[LeetCode] 38. Count and Say

ProblemPermalink

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 substrings such that each substring contains exactly one unique digit. Then for each substring, say the number of digits, then say the digit. Finally, concatenate every said digit.

For example, the saying and conversion for digit string "3322251":

Given a positive integer n, return the nth term of the count-and-say sequence.

Example 1:

Input: n = 1
Output: "1"
Explanation: This is the base case.

Example 2:

Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = say "1" = one 1 = "11"
countAndSay(3) = say "11" = two 1's = "21"
countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"

Constraints:

• 1 <= n <= 30

SolutionPermalink

public class Solution {
    public String countAndSay(int n) {
        String result = "1";
        for (int i = 1; i < n; i++)
            result = helper(result);
        return result;
    }
    public String helper(String s) {
        StringBuilder sb = new StringBuilder();
        char c = s.charAt(0);
        int count = 1;
        // 첫 번째 문자는 반복문에 사용될 필요가 없기 때문에 두 번째 문자부터 반복문에 사용함
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == c)
                count++;
            else
            {
                sb.append(count);
                sb.append(c);
                c = s.charAt(i);
                count = 1;
            }
        }
        sb.append(count);
        sb.append(c);
        return sb.toString();
    }
}

ExplanationPermalink

• 인수가 n일 때 반환되는 문자열이 독립적으로 존재하는 것이 아니라, 인수가 n - 1일 때 반환하는 문자열을 통해 인수가 n일 때 반환하는 문자열을 구할 수 있다. 이는 n - 1번의 반복을 통해 인수가 n일 때 반환되는 문자열을 구해야 한다는 의미가 된다.
• 인수가 n - 1일 때 반환되는 문자열을 통해 인수가 n일 때 반환되는 문자열을 구하기 위한 함수를 작성하여, 해당 함수를 n - 1번 실행하면 문제를 쉽게 해결할 수 있다.
• 함수를 작성하기 전, 함수를 통해 생성된 문자열로 다시 함수를 호출하는 반복을 n - 1번 실행하도록 for반복문을 작성한다.

  String result = "1";
  for (int i = 1; i < n; i++)
    result = helper(result);
  

• 인수가 n - 1일 때 반환되는 문자열을 통해 인수가 n일 때 반환되는 문자열을 구하기 위한 함수를 작성하도록 한다.

  public String helper(String s) {
    StringBuilder sb = new StringBuilder();
    char c = s.charAt(0);
    int count = 1;
    // 첫 번째 문자는 반복문에 사용될 필요가 없기 때문에 두 번째 문자부터 반복문에 사용함
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == c)
            count++;
        else
        {
            sb.append(count);
            sb.append(c);
            c = s.charAt(i);
            count = 1;
        }
    }
    sb.append(count);
    sb.append(c);
    return sb.toString();
  }
  

• 최종적으로 반환된 문자열 result를 반환하도록 한다.

  return result;