Coding Exercise - Find Letter Case Permutation with DFS 编程练习题：找出字符串的所有大小小组合

justyy (82)in #programming • 6 years ago (edited)

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 at most 12. S will consist only of letters or digits.

DFS (Depth First Search) using Recursion

Starting from the first letter, we recursively concat it. Each letter could have maximum two variants (lowercase and uppercase). When we reach the end of the string, we push the current string to the result vector.

DFS can be implemented using a helper function in recursion.

class Solution {
public:
    vector<string> letterCasePermutation(string S) {
        search("", S, 0, S.length() - 1);
        return r;
    }
    
private:
    vector<string> r;
    void search(string cur, string S, int i, int j) {
        if (i > j) {
            r.push_back(cur);
            return ;
        }
        auto ch1 = string(1, std::toupper(S[i])); // convert character to string
        search(cur + ch1, S, i + 1, j);
        auto ch2 = string(1, std::tolower(S[i]));
        if (ch2 != ch1) { // if it has a uppercase or lowercase
            search(cur + ch2, S, i + 1, j);
        }
    }
};

Reposted to my blog for better indexing.

Support me and my work as a witness - witness thread by

voting me here, or
voting me as a proxy.

Thank you! Some of My Contributions: SteemIt Tutorials, Robots, Tools and APIs

题意：给定一个字符串，输出所有字符大小写都可以组成的字符串。
如： "ab1" 能成生 ["ab1", "Ab1", "aB1", "AB1"]

DFS 深度优先 - 递归

我们可以从字符串的开头递归的把当前字符给添加到最终的字符串中，当当前字符是字母的时候，就有两种可能了。当到达字符串尾部的时候我们把当前字符串添加到结果数组中即可。

class Solution {
public:
    vector<string> letterCasePermutation(string S) {
        search("", S, 0, S.length() - 1);
        return r;
    }
    
private:
    vector<string> r;
    void search(string cur, string S, int i, int j) {
        if (i > j) {
            r.push_back(cur);
            return ;
        }
        auto ch1 = string(1, std::toupper(S[i])); // 把字符转成串
        search(cur + ch1, S, i + 1, j);
        auto ch2 = string(1, std::tolower(S[i]));
        if (ch2 != ch1) { // 如果是字母
            search(cur + ch2, S, i + 1, j);
        }
    }
};

刚刚同步到我的博客：https://justyy.com/archives/6445