leetcode : Letter Combinations of a Phone Number

runtime 0 ms, beats 100% of cpp submissions
O(k^n) solution with explanation

tags: recursion

🔗 link

Letter Combinations of a Phone Number

📖 description

給定一個按鍵的輸入字串，枚舉出所有可能的表示意思

2 -> abc
3 -> def
4 -> ghi
5 -> jkl
6 -> mno
7 -> pqrs
8 -> tuv
9 -> wxyz

ex.
    digits = "23"
    output = ["ad","ae","af","bd","be","bf","cd","ce","cf"]

🧠 solution

一個經典的全排列題目，在每個階段都枚當前 index 的所有可能表示方式

⏳ time complexity

要枚舉每個 index 的所有可能字元，每個字元有 3 或 4 個可能，字串長度為 n ， 時間複雜度為 O(k^n)
總時間複雜度 O(k^n)

📝 code

class Solution {
public:
    vector<string> phone = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector<string> ans;
    void re(string& d,string& now,int ind){
        if(ind>=d.size()){
            ans.emplace_back(now);
            return;
        }
        for(int i=0;i<phone[d[ind]-'0'].size();i++){
            now+=phone[d[ind]-'0'][i];
            re(d,now,ind+1);
            now.pop_back();
        }
    }
    vector<string> letterCombinations(string& digits) {
        if(digits.size()==0) return {};
        ans.clear();
        string now;
        re(digits,now,0);
        return ans;
    }
};