<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 0017. 電話號碼的字母組合 ## 題目地址(17. 電話號碼的字母組合) <https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number> ## 題目描述 給定一個僅包含數字 2-9 的字符串,返回所有它能表示的字母組合。 ![](https://img.kancloud.cn/b5/92/b592cf690f5f00e7c2635fccd3043392_499x452.png) ``` <pre class="calibre18">``` 給出數字到字母的映射如下(與電話按鍵相同)。注意 1 不對應任何字母。 示例: 輸入:"23" 輸出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. 說明: 盡管上面的答案是按字典序排列的,但是你可以任意選擇答案輸出的順序。 ``` ``` ## 前置知識 - 回溯 ## 公司 - 阿里 - 百度 - 字節 - 騰訊 ## 思路 使用回溯法進行求解,回溯是一種通過窮舉所有可能情況來找到所有解的算法。如果一個候選解最后被發現并不是可行解,回溯算法會舍棄它,并在前面的一些步驟做出一些修改,并重新嘗試找到可行解。究其本質,其實就是枚舉。 如果沒有更多的數字需要被輸入,說明當前的組合已經產生。 如果還有數字需要被輸入: - 遍歷下一個數字所對應的所有映射的字母 - 將當前的字母添加到組合最后,也就是 str + tmp\[r\] ## 關鍵點 - 回溯 - 回溯模板 ## 代碼 - 語言支持:JS ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {string} digits * @return {string[]} */</span> <span class="hljs-keyword">const</span> letterCombinations = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">digits</span>) </span>{ <span class="hljs-keyword">if</span> (!digits) { <span class="hljs-keyword">return</span> []; } <span class="hljs-keyword">const</span> len = digits.length; <span class="hljs-keyword">const</span> map = <span class="hljs-keyword">new</span> <span class="hljs-params">Map</span>(); map.set(<span class="hljs-string">"2"</span>, <span class="hljs-string">"abc"</span>); map.set(<span class="hljs-string">"3"</span>, <span class="hljs-string">"def"</span>); map.set(<span class="hljs-string">"4"</span>, <span class="hljs-string">"ghi"</span>); map.set(<span class="hljs-string">"5"</span>, <span class="hljs-string">"jkl"</span>); map.set(<span class="hljs-string">"6"</span>, <span class="hljs-string">"mno"</span>); map.set(<span class="hljs-string">"7"</span>, <span class="hljs-string">"pqrs"</span>); map.set(<span class="hljs-string">"8"</span>, <span class="hljs-string">"tuv"</span>); map.set(<span class="hljs-string">"9"</span>, <span class="hljs-string">"wxyz"</span>); <span class="hljs-keyword">const</span> result = []; <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">generate</span>(<span class="hljs-params">i, str</span>) </span>{ <span class="hljs-keyword">if</span> (i == len) { result.push(str); <span class="hljs-keyword">return</span>; } <span class="hljs-keyword">const</span> tmp = map.get(digits[i]); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> r = <span class="hljs-params">0</span>; r < tmp.length; r++) { generate(i + <span class="hljs-params">1</span>, str + tmp[r]); } } generate(<span class="hljs-params">0</span>, <span class="hljs-string">""</span>); <span class="hljs-keyword">return</span> result; }; ``` ``` **復雜度分析** N + M 是輸入數字的總數 - 時間復雜度:O(3^N \* 4^M) - 空間復雜度:O(3^N \* 4^M) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看