C++ Coding Exercise – Find Letter Case Permutation with DFS


learn-to-code C++ Coding Exercise - Find Letter Case Permutation with DFS algorithms c / c++ DFS

learn-to-code

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.

The DFS can be implemented using a helper function in recursion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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);
        }
    }
};
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);
        }
    }
};

You may also like: C++编程练习题:找出字符串的所有大小小组合

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
329 words
Last Post: Algorithms to Find Maximum Depth of N-ary Tree (C++)
Next Post: C++ Coding Exercise - Find All Duplicates in an Array

The Permanent URL is: C++ Coding Exercise – Find Letter Case Permutation with DFS

Leave a Reply