784.Letter Case Permutation

Tags: Easy Backtracking Bit Manipulation

Links: https://leetcode.com/problems/letter-case-permutation/

---

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

Examples:
Input: S = "a1b2"
Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Input: S = "3z4"
Output: ["3z4", "3Z4"]

Input: S = "12345"
Output: ["12345"]

Note:

• S will be a string with length between 1 and 12.
• S will consist only of letters or digits.

---

class Solution {
public:
    vector<string> letterCasePermutation(string S) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (S.size() == 0) return {};
        if (S.size() == 1) {
            if (isdigit(S[0])) return {S};
            else {
                string s1, s2;
                s1.push_back(toupper(S[0]));
                s2.push_back(tolower(S[0]));
                return {s1, s2};
            }
        }

        vector<string> before = letterCasePermutation(S.substr(1));
        vector<string> res;
        if (isdigit(S[0])) {
            for (auto e : before) {
                string tmp;
                tmp.push_back(S[0]);
                tmp += e;
                res.push_back(tmp);
            }
        }
        else {
            for (auto e : before) {
                string tmp;
                tmp.push_back(toupper(S[0]));
                tmp += e;
                res.push_back(tmp);
            }
            for (auto e : before) {
                string tmp;
                tmp.push_back(tolower(S[0]));
                tmp += e;
                res.push_back(tmp);
            }
        }

        return res;
    }
};

递归求解即可，每次判断当前字符是否是数字即可。

非递归的解法，需要一定技巧性，每次用一个变量len记录结果数组的长度，遇到字母时候将第i位的结果复制一个放入数组，然后更新i和len + i的结果。

class Solution {
public:
    vector<string> letterCasePermutation(string S) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        vector<string> res{""};
        for (auto e : S) {
            int len = res.size();
            if (isdigit(e)) {
                //这里记得是引用，否则出错
                for (auto & obj : res) obj.push_back(e);
            }
            else {
                for (int i = 0; i < len; ++i) {
                    res.push_back(res[i]);
                    res[i].push_back(tolower(e));
                    res[i + len].push_back(toupper(e));
                }
            }
        }

        return res;
    }
};

迭代的方法将速度从16ms提高到了4ms。

另外就是根据提示，总长度不超过12，那么可以考虑用位运算来解决。

class Solution {
public:
    vector<string> letterCasePermutation(string S) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        vector<string> res;
        int cnt = 0;
        for (const char & e : S) {
            if (!isdigit(e)) ++cnt;
        }

        for (int i = 0; i < (1 << cnt); ++i) {
            int pos = 0;
            string word;
            for (int j = 0; j < S.size(); ++j) {
                if (isdigit(S[j])) {
                    word.push_back(S[j]);
                }
                else {
                    if ((i >> pos++) & 1) {
                        word.push_back(tolower(S[j]));
                    }
                    else {
                        word.push_back(toupper(S[j]));
                    }
                }
            }
            res.push_back(word);
        }

        return res;
    }
};