Skip to content

Latest commit

 

History

History
118 lines (109 loc) · 23.5 KB

17 Letter combination 递归 DFS BFS.md

File metadata and controls

118 lines (109 loc) · 23.5 KB

Given a string containing digits from 2-9 inclusive, return all
possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is
given below. Note that 1 does not map to any letters.

题目

递归遍历（深度遍历）

class Solution:
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        phone = {'2': ['a', 'b', 'c'],
                 '3': ['d', 'e', 'f'],
                 '4': ['g', 'h', 'i'],
                 '5': ['j', 'k', 'l'],
                 '6': ['m', 'n', 'o'],
                 '7': ['p', 'q', 'r', 's'],
                 '8': ['t', 'u', 'v'],
                 '9': ['w', 'x', 'y', 'z']}

    <span class="token keyword">def</span> <span class="token function">backtrack</span><span class="token punctuation">(</span>combination<span class="token punctuation">,</span> next_digits<span class="token punctuation">)</span><span class="token punctuation">:</span>
        <span class="token comment"># if there is no more digits to check</span>
        <span class="token comment">#边界情况</span>
        <span class="token keyword">if</span> <span class="token builtin">len</span><span class="token punctuation">(</span>next_digits<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">:</span>
            <span class="token comment"># the combination is done</span>
            output<span class="token punctuation">.</span>append<span class="token punctuation">(</span>combination<span class="token punctuation">)</span>
        <span class="token comment"># if there are still digits to check</span>
        <span class="token keyword">else</span><span class="token punctuation">:</span>
            <span class="token comment"># iterate over all letters which map </span>
            <span class="token comment"># the next available digit</span>
            <span class="token keyword">for</span> letter <span class="token keyword">in</span> phone<span class="token punctuation">[</span>next_digits<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">:</span>
                <span class="token comment"># append the current letter to the combination</span>
                <span class="token comment"># and proceed to the next digits</span>
                <span class="token comment">#遍历每一个letter的子空间</span>
                backtrack<span class="token punctuation">(</span>combination <span class="token operator">+</span> letter<span class="token punctuation">,</span> next_digits<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">:</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
                
    output <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>
    <span class="token keyword">if</span> digits<span class="token punctuation">:</span>
        backtrack<span class="token punctuation">(</span><span class="token string">""</span><span class="token punctuation">,</span> digits<span class="token punctuation">)</span>
    <span class="token keyword">return</span> output

示意图

队列（层次遍历）

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        phone = {'2': ['a', 'b', 'c'],
                 '3': ['d', 'e', 'f'],
                 '4': ['g', 'h', 'i'],
                 '5': ['j', 'k', 'l'],
                 '6': ['m', 'n', 'o'],
                 '7': ['p', 'q', 'r', 's'],
                 '8': ['t', 'u', 'v'],
                 '9': ['w', 'x', 'y', 'z']}
        if not digits:
            return []
        ans = ['']
        for cur in range(len(digits)):
            while len(ans[0]) == cur:#判断上一层的字符串是否全都被处理完了
                cur_str = ans.pop(0)
                for letter in phone[digits[cur]]:
                    ans.append(cur_str + letter)
        return ans

赖皮解法

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        m = {
            '2': list('abc'),
            '3': list('def'),
            '4': list('ghi'),
            '5': list('jkl'),
            '6': list('mno'),
            '7': list('pqrs'),
            '8': list('tuv'),
            '9': list('wxyz'),
            }
        if not digits: return []
        ls1 = ['']
        for i in digits:
            ls1 = [x + y for x in ls1 for y in m[i]]
        return ls1

相当于

```gml
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        phone = {'2': ['a', 'b', 'c'],
         '3': ['d', 'e', 'f'],
         '4': ['g', 'h', 'i'],
         '5': ['j', 'k', 'l'],
         '6': ['m', 'n', 'o'],
         '7': ['p', 'q', 'r', 's'],
         '8': ['t', 'u', 'v'],
         '9': ['w', 'x', 'y', 'z']}

    <span class="token keyword">if</span> <span class="token operator">not</span> digits<span class="token punctuation">:</span><span class="token keyword">return</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>
    
    res <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token string">''</span><span class="token punctuation">]</span>
    tem <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>
    <span class="token keyword">for</span> i <span class="token keyword">in</span> digits<span class="token punctuation">:</span>
        <span class="token comment">#res = [x+y for x in res for y in phone[i]]</span>
        <span class="token keyword">for</span> x <span class="token keyword">in</span> res<span class="token punctuation">:</span>
            <span class="token keyword">for</span> y <span class="token keyword">in</span> phone<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">:</span>
                tem<span class="token punctuation">.</span>append<span class="token punctuation">(</span>x<span class="token operator">+</span>y<span class="token punctuation">)</span>
        res <span class="token operator">=</span> tem
        tem<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>
            
    <span class="token keyword">return</span> res