LEETCODE - 1415. The k-th Lexicographical String of All Happy Strings of Length n

https://leetcode.com/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n/

 

consists only of letters of the set ['a', 'b', 'c'].

문자열 배열에 a b c 세개의 문자가 있고

입력으로 들어오는 n 은 문자열의 길이 k 는 n 길이 만큼이 조합으로 만들어진 무자열 배열의 크기를 뜻 한다.

(아아~ 한국말 어렵다)

 

문제의 조건에서

s[i] != s[i + 1] for all values of i from 1 to s.length - 1 (string is 1-indexed).

이전의 글자는 그 다음 글자와 같을 수 없다.

 

만약 N 이 2일때 a,b,c 의 조합 문자는{aa, ab, ac, ba, bb, bc, ca, cb, cc} 를 만들 수 있으나.

같은 글자가 연속으로 올수 없으니 {ab,ac,ba,bc,ca,cb} 가 유효한 집합이 된다.

 

class Solution {
public:
    vector<string> arr;
    void rec(string& s, int remain) {
        if (remain == 0) {
            arr.push_back(s);
            return;
        }

        char prevChar = 'z';
        if (s.size() != 0) {
            prevChar = s.back();
        }


        for (int i = 0; i < 3; i++) {
            char crtChar = 'a' + i;

            if (prevChar == crtChar)
                continue;

            s.push_back(crtChar);
            rec(s, remain - 1);
            s.pop_back();
        }
    }
    
    string getHappyString(int n, int k) {
        string s;
        rec(s, n);
        sort(arr.begin(), arr.end());
        if (arr.size() < k) {
            return "";
        }
        else
            return arr[k - 1];
    }
};