LeetCode - 784 - Tung in ECNU


LeetCode - 784

题目描述

给定一个字符串S,通过将字符串S中的每个字母转变大小写,我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

示例 :

输入: S = "a1b2"
输出: ["a1b2", "a1B2", "A1b2", "A1B2"]

输入: S = "3z4"
输出: ["3z4", "3Z4"]

输入: S = "12345"
输出: ["12345"]

解题思路

  1. 根据题意,一个字母有大小写两种可能,所以一共有 $$2^{n}$$ 种可能,n是字符串中字母的个数
  2. 以a1b2为例,遍历字符数组,当遇到a时有两种可能,这两种情况在遍历到b时又出现了两种可能,所以考虑回溯算法
  3. 编写回溯算法,满足以下条件

    1. 遇到非字母,往后继续递归
    2. 遇到字母,转化之后继续递归
    3. 遍历到数组末尾后用ArrayList存起来

字母大小写转化

在ASCII码表中A和a相差了32,可以表示为$$2^5$$,于是可以考虑用异或来进行转化

以A为例,在码表中的编码是0100 0001,而a在码表中的编码是0110 0001

只要对加粗的那一位进行异或操作就可以了,也就是^(1<<5)(这个数位右边的数位个数为5)

回溯算法

递归是一种算法结构,回溯是一种算法思想,回溯可以用递归来实现。

public void dg(char[] s, int i, List<String> ans) {
    if (i == s.length) {
        ans.add(String.valueOf(s));
        return;
    }
    dg(s, i + 1, ans);
    if (s[i] < '0' || s[i] > '9') { //题中已说明给定的字符串中只含数字或字母
        s[i] ^= (1 << 5); //大小写转化
        dg(s, i + 1, ans);
    }

}

JAVA 代码

public List<String> letterCasePermutation(String S) {
    List<String> ans = new ArrayList<>();
    dg(S.toCharArray(), 0, ans);
    return ans;
}

public void dg(char[] s, int i, List<String> ans) {
    if (i == s.length) { //边界条件
        ans.add(String.valueOf(s));
        return;
    }
    dg(s, i + 1, ans);
    if (s[i] < '0' || s[i] > '9') {
        s[i] ^= (1 << 5);
        dg(s, i + 1, ans);
    }

}

本文链接:

https://noahtung.xyz/index.php/archives/23/