###### tags: `LeetCode` `Medium` `Recursion` `String` `Queue`
# LeetCode #784 [Letter Case Permutation](https://leetcode.com/problems/letter-case-permutation/)
### (Medium)

給定一個字符串S，通過將字符串S中的每個字母轉變大小寫，我們可以獲得一個新的字符串。返回所有可能得到的字符串集合。

---

與電話題類似, 使用Queue, 若讀入的字符為數字, 則將Queue中的所有字串全部加上該數字字符, 而若字符為英文字母, 則將Queue中的所有字串分別加上字母的大小寫, 並把字串放回Queue中為下一個字符使用。

---

class Solution {
public:
    vector<string> letterCasePermutation(string s) {
        queue<string> q;
        q.push("");
        for(auto c:s){
            if(isalpha(c)){//c is a letter
                for(int i=q.size();i>0;i--){
                    string s=q.front();q.pop();
                    c=tolower(c);
                    q.push(s+c);
                    c=toupper(c);
                    q.push(s+c);
                }
            }
            else{//c is a digit
                for(int i=q.size();i>0;i--){
                    string s=q.front();q.pop();
                    q.push(s+c);
                }
            }
        }
        vector<string> ans;
        for(int i=q.size();i>0;i--){
            string s=q.front();q.pop();
            ans.push_back(s);
        }
        return ans;
    }
};