leetcode筆記：Leetcode Letter Combinations of a Phone Number

一. 題目描述

Given a digit string, 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.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

二. 題目分析

題目的大意是，在手機上按字母，給出所按的數字鍵，問所有的按的字母的情況。該題使用DFS即可完成，難度不大。

三. 示例代碼

class Solution {
public:
    vector result;
    vector letterCombinations(string digits) {
        if (digits == "") return result;
        static string k[8] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        string temp = "";
        dfs(digits, temp, k);
        return result;
    }

private:
    void dfs(string dig, string temp, string str[])
    {
        // find函數用於尋找某個序列的在string中第一次出現的位置，防止重復
        if (dig.size() == 0 && find(result.begin(), result.end(), temp) == result.end()) 
        {
            result.push_back(temp);
            return;
        }
        else
        {
            for (int i = 0; i < str[dig[0] - '2'].size(); ++i)
            {
                temp += str[dig[0] - '2'][i]; // 在最後添加一個字符
                dfs(dig.substr(1, dig.size()), temp, str);
                temp = temp.substr(0, temp.size() - 1); // 去掉最後一個字符
            }
            return;
        }
    }
};