784. Letter Case Permutation

public class Solution {
    public IList<string> LetterCasePermutation(string S) {
        var ans = new List<List<char>> { new List<char>() };
        foreach (var c in S) {
            int n = ans.Count;
            if (char.IsLetter(c)) {
                for (int i = 0; i < n; i++) {
                    var current = new List<char>(ans[i]);
                    ans.Add(current);
                    ans[i].Add(char.ToLower(c));
                    ans[n + i].Add(char.ToUpper(c));
                }
            } else {
                for (int i = 0; i < n; i++) {
                    ans[i].Add(c);
                }
            }
        }
        return ans.Select(list => new string(list.ToArray())).ToList();
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<string> LetterCasePermutation(string S) {
        var ans = new List<List<char>> { new List<char>() };
        foreach (var c in S) {
            int n = ans.size();
            if (char.IsLetter(c)) {
                for (int i = 0; i < n; i++) {
                    var current = new List<char>(ans[i]);
                    ans.push_back(current);
                    ans[i].push_back(char.ToLower(c));
                    ans[n + i].push_back(char.ToUpper(c));
                }
            } else {
                for (int i = 0; i < n; i++) {
                    ans[i].push_back(c);
                }
            }
        }
        return ans.Select(list => new string(list.ToArray())).ToList();
    }
}

class Solution {
    public List<String> letterCasePermutation(String S) {
        List<List<Character>> ans = new ArrayList<>();
        ans.add(new ArrayList<>());

        for (char c : S.toCharArray()) {
            int n = ans.size();
            if (Character.isLetter(c)) {
                for (int i = 0; i < n; i++) {
                    List<Character> current = new ArrayList<>(ans.get(i));
                    ans.add(current);
                    ans.get(i).add(Character.toLowerCase(c));
                    ans.get(n + i).add(Character.toUpperCase(c));
                }
            } else {
                for (int i = 0; i < n; i++) {
                    ans.get(i).add(c);
                }
            }
        }

        List<String> result = new ArrayList<>();
        for (List<Character> list : ans) {
            StringBuilder sb = new StringBuilder();
            for (char c : list) {
                sb.append(c);
            }
            result.add(sb.toString());
        }
        return result;
    }
}

class Solution:
    def letterCasePermutation(self, S):
        ans = [[]]

        for char in S:
            n = len(ans)
            if char.isalpha():
                for i in range(n):
                    ans.append(ans[i][:])
                    ans[i].append(char.lower())
                    ans[n+i].append(char.upper())
            else:
                for i in range(n):
                    ans[i].append(char)

        return list(map("".join, ans))

package main

import (
    "strings"
    "unicode"
)

func letterCasePermutation(S string) []string {
    ans := [][]rune{{}}

    for _, c := range S {
        n := len(ans)
        if unicode.IsLetter(c) {
            for i := 0; i < n; i++ {
                ans = append(ans, append([]rune{}, ans[i]...))
                ans[i] = append(ans[i], unicode.ToLower(c))
                ans[n+i] = append(ans[n+i], unicode.ToUpper(c))
            }
        } else {
            for i := 0; i < n; i++ {
                ans[i] = append(ans[i], c)
            }
        }
    }

    result := make([]string, len(ans))
    for i, r := range ans {
        result[i] = string(r)
    }
    return result
}

Algorithm

Если следующий символ c является буквой, то мы удвоим все слова в нашем текущем ответе, и добавим lowercase(c) к каждому слову в первой половине, и uppercase(c) к каждому слову во второй половине.

Если c является цифрой, мы добавим его к каждому слову.

Продолжайте процесс для всех символов в строке, чтобы получить все возможные комбинации.

😎