字母大小写全排列-784
sl1673495 opened this issue · 1 comments
给定一个字符串 S,通过将字符串 S 中的每个字母转变大小写,我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
示例:
输入: S = "a1b2"
输出: ["a1b2", "a1B2", "A1b2", "A1B2"]
输入: S = "3z4"
输出: ["3z4", "3Z4"]
输入: S = "12345"
输出: ["12345"]
注意:
S 的长度不超过12。
S 仅由数字和字母组成。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/letter-case-permutation
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
这题不需要交换顺序排列组合,所以会简单点,只需要把当前第一位的字母分别大小写处理(如果是数字就直接不动)拼接在前面已经处理好的字符串后,带上截取掉第一位后的剩余字符串交给下一轮递归,直到拼接的字符长度符合 S 的长度即可终止。
/**
* @param {string} S
* @return {string[]}
*/
let letterCasePermutation = function (S) {
let res = []
let helper = (prev, rest) => {
if (prev.length === S.length) {
res.push(prev)
return
}
let char = rest[0]
let word1 = prev + char
let nextRest = rest.substring(1)
if (!isNaN(Number(char))) {
helper(word1, nextRest)
return
} else {
let upperChar = char.toUpperCase()
let char2 = upperChar === char ? char.toLowerCase() : upperChar
let word2 = prev + char2
helper(word1, nextRest)
helper(word2, nextRest)
}
}
helper("", S)
return res
}
const letterCasePermutation = function (s) {
let res = []
let str = ""
let len = s.length
dfs(0)
return res
function dfs(startIndex) {
if (str.length === len) {
res.push(str)
return
}
if (isNaN(s[startIndex])) {
str=str+s[startIndex].toLowerCase()
dfs(startIndex + 1)
str = str.slice(0, str.length - 1)
str = str + s[startIndex].toUpperCase()
dfs(startIndex + 1)
str = str.slice(0, str.length - 1)
} else {
str = str + s[startIndex]
dfs(startIndex + 1)
str=str.slice(0, str.length - 1)
}
}
};