###### tags: `LeetCode` `Medium` `String` `Queue`
# LeetCode #17 [Letter Combinations of a Phone Number](https://leetcode.com/problems/letter-combinations-of-a-phone-number/)
### (Medium)

給定一個僅包含數字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。

給出數字到字母的映射如下（與電話按鍵相同）。注意 1 不對應任何字母。

---
由於要列出所有組合, 因此可以使用Queue儲存第i位digit時的所有組合, 等讀到第i+1位digit時, 將Queue中的所有元素配上第i+1位digit所有的英文字母, 成為第i+1位digit的組合, 再將組合放回Queue中為下一位digit所用。

最後再將Queue中的元素放入vector<string>中回傳即可。

---

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(!digits.size())return {};
        vector<string> pad = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        queue<string> q;
        q.push("");
        for(auto digit:digits){
            for(int i=q.size();i>0;i--){
                string s=q.front();q.pop();
                for(auto c:pad[digit-'0']){
                    q.push(s+c);
                }
            }
        }
        vector<string> ans;
        for(int i=q.size();i>0;i--){
            ans.push_back(q.front());
            q.pop();
        }
        return ans;
    }
};

---
LeetCode版, 由於上面的方法需要額外一個Queue的空間, 因此空間複雜度不太好, 這個方法透過vector swap取代Queue的push跟pop, 而在迴圈結束後用來swap的vector的空間會被釋放, 所以空間複雜度更好。

class Solution {
public:
    const vector<string> pad = {
        "", "", "abc", "def", "ghi", "jkl",
        "mno", "pqrs", "tuv", "wxyz"
    };
    
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
		vector<string> result;
        result.push_back("");
        
        for(auto digit: digits) {
            vector<string> tmp;
            for(auto candidate: pad[digit - '0']) {
                for(auto s: result) {
                    tmp.push_back(s + candidate);
                }
            }
            result.swap(tmp);// <-tmp與result交互使用
        }
        return result;
    }
};