{"id":6635,"date":"2020-04-18T12:37:04","date_gmt":"2020-04-18T19:37:04","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6635"},"modified":"2020-04-18T12:37:14","modified_gmt":"2020-04-18T19:37:14","slug":"leetcode-1415-the-k-th-lexicographical-string-of-all-happy-strings-of-length-n","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-1415-the-k-th-lexicographical-string-of-all-happy-strings-of-length-n\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1415. The k-th Lexicographical String of All Happy Strings of Length n"},"content":{"rendered":"\n<p>A&nbsp;<strong>happy string<\/strong>&nbsp;is a string that:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>consists only of letters of the set&nbsp;<code>['a', 'b', 'c']<\/code>.<\/li><li><code>s[i] != s[i + 1]<\/code>&nbsp;for all values of&nbsp;<code>i<\/code>&nbsp;from&nbsp;<code>1<\/code>&nbsp;to&nbsp;<code>s.length - 1<\/code>&nbsp;(string is 1-indexed).<\/li><\/ul>\n\n\n\n<p>For example, strings&nbsp;<strong>&#8220;abc&#8221;, &#8220;ac&#8221;, &#8220;b&#8221;<\/strong>&nbsp;and&nbsp;<strong>&#8220;abcbabcbcb&#8221;<\/strong>&nbsp;are all happy strings and strings&nbsp;<strong>&#8220;aa&#8221;, &#8220;baa&#8221;<\/strong>&nbsp;and&nbsp;<strong>&#8220;ababbc&#8221;<\/strong>&nbsp;are not happy strings.<\/p>\n\n\n\n<p>Given two integers&nbsp;<code>n<\/code>&nbsp;and&nbsp;<code>k<\/code>, consider a list of all happy strings of length&nbsp;<code>n<\/code>&nbsp;sorted in lexicographical order.<\/p>\n\n\n\n<p>Return&nbsp;<em>the kth string<\/em>&nbsp;of this list or return an&nbsp;<strong>empty string<\/strong>&nbsp;if there are less than&nbsp;<code>k<\/code>&nbsp;happy strings of length&nbsp;<code>n<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 1, k = 3\n<strong>Output:<\/strong> \"c\"\n<strong>Explanation:<\/strong> The list [\"a\", \"b\", \"c\"] contains all happy strings of length 1. The third string is \"c\".\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 1, k = 4\n<strong>Output:<\/strong> \"\"\n<strong>Explanation:<\/strong> There are only 3 happy strings of length 1.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 3, k = 9\n<strong>Output:<\/strong> \"cab\"\n<strong>Explanation:<\/strong> There are 12 different happy string of length 3 [\"aba\", \"abc\", \"aca\", \"acb\", \"bab\", \"bac\", \"bca\", \"bcb\", \"cab\", \"cac\", \"cba\", \"cbc\"]. You will find the 9th string = \"cab\"\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 2, k = 7\n<strong>Output:<\/strong> \"\"\n<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 10, k = 100\n<strong>Output:<\/strong> \"abacbabacb\"\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= n &lt;= 10<\/code><\/li><li><code>1 &lt;= k &lt;= 100<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DFS<\/strong><\/h2>\n\n\n\n<p>Generate the happy strings in lexical order, store the k-th one.<br>Time complexity: O(n + k)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  string getHappyString(int n, int k) {\n    string ans;\n    string cur;\n    function<void()> dfs = [&]() {\n      if (k <= 0) return;\n      if (cur.length() == n) {\n        if (--k == 0) ans = cur;\n        return;\n      }      \n      for (char ch = 'a'; ch <= 'c'; ++ch) {\n        if (!cur.empty() &#038;&#038; ch == cur.back()) continue;\n        cur.push_back(ch);\n        dfs();\n        cur.pop_back();\n      }      \n    };\n    dfs();\n    return k > 0 ? \"\" : ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>A&nbsp;happy string&nbsp;is a string that: consists only of letters of the set&nbsp;[&#8216;a&#8217;, &#8216;b&#8217;, &#8216;c&#8217;]. s[i] != s[i + 1]&nbsp;for all values of&nbsp;i&nbsp;from&nbsp;1&nbsp;to&nbsp;s.length &#8211; 1&nbsp;(string is&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[33,42,4],"class_list":["post-6635","post","type-post","status-publish","format-standard","hentry","category-searching","tag-dfs","tag-search","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6635","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6635"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6635\/revisions"}],"predecessor-version":[{"id":6637,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6635\/revisions\/6637"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6635"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6635"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6635"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}