Re: [閒聊] 每日LeetCode

[yam276 (史萊哲林的優等生)]

17. Letter Combinations of a Phone Number

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

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

叫你用智障型手機的數字鍵與其數個對應字母，

來列出輸入數字字串的可能字母字串們。


Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]


昨天那題的進階版，用BackTracking遞迴來做

先建立字母對應表，然後每個level取出對應的字母集合去拼


Code:

class Solution
{
public:
    vector<string> letterCombinations(string digits)
    {
        if (digits.empty())
            return m_result;

        m_letters = {
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };

        BackTracking(0, digits, "");

        return m_result;
    }

    void BackTracking(int level, string digits, string curStr)
    {
        if (level == digits.length())
        {
            m_result.push_back(curStr);
            return;
        }

        char digit = digits[level];
        string letters = m_letters[digit];

        for (auto letter : letters)
        {
            curStr.push_back(letter);
            BackTracking(level + 1, digits, curStr);
            curStr.pop_back();
        }
    }

private:
    unordered_map<char, string> m_letters;
    vector<string> m_result;
};


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.249.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1691066135.A.32E.html
※ 編輯: yam276 (123.193.249.242 臺灣), 08/03/2023 20:36:16
→ Rushia: 大師