Create 1415.The k-th-Lexicographical-String-of-All-Happy-Strings-of-Length-n_v1.cpp

wisdompeak · web-flow · commit fd30dfd89b3f · 2021-01-27T02:49:35.000-08:00
diff --git a/Recursion/1415.The k-th-Lexicographical-String-of-All-Happy-Strings-of-Length-n/1415.The k-th-Lexicographical-String-of-All-Happy-Strings-of-Length-n_v1.cpp b/Recursion/1415.The k-th-Lexicographical-String-of-All-Happy-Strings-of-Length-n/1415.The k-th-Lexicographical-String-of-All-Happy-Strings-of-Length-n_v1.cpp
@@ -0,0 +1,48 @@
+class Solution {
+    unordered_set<string>rets;
+    string ans;
+    int N,K;
+public:
+    string getHappyString(int n, int k) 
+    {
+        string s;
+        ans = "";
+        N = n;
+        K = k;
+        DFS(0,s);        
+        return ans;
+    }
+    
+    void DFS(int cur, string s)
+    {
+        if (cur==N)
+        {
+            rets.insert(s);
+            if (rets.size()==K)
+                ans = s;
+            return;
+        }
+        
+        if (ans!="") return;
+        
+        if (cur==0)
+        {
+            for (auto ch='a'; ch<='c'; ch++)
+            {
+                s.push_back(ch);
+                DFS(cur+1, s);
+                s.pop_back();
+            }
+        }
+        else
+        {
+            for (auto ch='a'; ch<='c'; ch++)
+            {
+                if (ch==s.back()) continue;
+                s.push_back(ch);
+                DFS(cur+1, s);
+                s.pop_back();
+            }            
+        }
+    }
+};
