38. Count and Say
Problem
The count-and-say sequence is a sequence of digit strings defined by the recursive formula:
countAndSay(1) = "1"
countAndSay(n) is the way you would "say" the digit string from countAndSay(n-1), which is then converted into a different digit string.
To determine how you "say" a digit string, split it into the minimal number of groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.
Example
Input: n = 1
Output: "1"
Explanation: This is the base case.
Code (20. 12. 08)
class Solution {
public String countAndSay(int n) {
// 재귀니까 종료 조건이 반드시 필요
if (n == 1) {
return "1";
}
// Convert 되기 전 값
String ans = countAndSay(n - 1);
// Convert 된 후 값
return read(ans);
}
public String read(String ans) {
// 다루는 값은 0~9이므로
// 친근하게 배열 값으로 Counting을 하기로 생각함
int[] countArray = new int[100];
countArray[ans.charAt(0)]++;
StringBuilder sb = new StringBuilder();
for (int i = 1; i < ans.length(); i++) {
if (countArray[ans.charAt(i)] == 0) {
sb.append(countArray[ans.charAt(i - 1)]);
sb.append(ans.charAt(i - 1));
countArray[ans.charAt(i - 1)] = 0;
}
countArray[ans.charAt(i)]++;
}
sb.append(countArray[ans.charAt(ans.length() - 1)]);
sb.append(ans.charAt(ans.length() - 1));
return sb.toString();
}
}