字符串

最长回文子串

思路：见代码

class Solution {
    public String longestPalindrome(String s) {
        //左边界
        int resL=0;
        //右边界
        int resR=0;
        for(int i=0;i<s.length();i++){
            //有两种情况：1为一个中心点 2为两个中心点
            for(int j=0;j<=1;j++){
                int l=i;
                int r=i+j;
                //两边扩张
                while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){
                    l--;
                    r++;
                }
                //回到正确的位置
                l++;
                r--;
                if(r-l>resR-resL){
                    resL=l;
                    resR=r;
                }


            }
        }
        return s.substring(resL,resR+1);
    }
}

有效的括号

思路：

1. 遇到右括号入栈，遇到左括号则与栈顶比较

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        for(char c:s.toCharArray()){
            if(c=='['||c=='{'||c=='('){
              stack.add(c);
            }
            else if(!stack.isEmpty()&&equals(stack.peek(),c)){
                stack.pop();
            }
            else return false;
        }
        //为什么不直接返回 true 
        //"[" 这种情况就得判Stack是否为空
        return stack.isEmpty();
    }
    public boolean equals(char a,char b){
        if(a=='['&&b==']'){
           return true;
        }
        else if(a=='{'&&b=='}'){
           return true;
        }
        else if(a=='('&&b==')'){
           return true;
        }
        return false;
    }
}

字符串相加

题目：大数相加

思路：

1. 倒序相加，p1,p2从后面遍历字符串，然后at(p1) 和 at(p2) 进行相加，若p1 or p2 <0 就at(p) =0
2. 相加过程：sum = at(p1) +at(p2) + pos（上一次运算进的位），然后当前位置的相加后的值 = sum%10，下一次进位 sum/10
3. 后面如果出现 9+1这边，while结束后 if(pos > 1) append(1)
4. 最后结果倒置 reverse()

class Solution {
    public String addStrings(String num1, String num2) {
        int p1=num1.length()-1;
        int p2=num2.length()-1;
        int pos=0;
        StringBuilder res=new StringBuilder();
        while(p1>=0||p2>=0){
            int n1=p1>=0?num1.charAt(p1)-'0':0;
            int n2=p2>=0?num2.charAt(p2)-'0':0;
            int sum=n1+n2+pos;
            res.append(sum%10);
            pos=(sum)/10;
            p1--;
            p2--;
        }
        if(pos>0){
            res.append(1);
        }
        return res.reverse().toString();
    }
}

大数相减要怎么做？或者说num1 为负数呢

复原IP地址

思路：

1. 第一步要要思考，当下有几种选择？
   • 以 “25525511135” 为例，第一步时我们有几种选择？
     1. 选 “2” 作为第一个片段
     2. 选 “25” 作为第一个片段
     3. 选 “255” 作为第一个片段
   1. 然后第二步的时候我们又有几种选择，切第二个片段时，又面临三种选择
   2. 这会向下分支，形成一棵树，我们用 DFS 去遍历所有选择，必要时提前回溯。

因为某一步的选择可能是错的，得不到正确的结果，不要往下做了。撤销最后一个选择，回到选择前的状态，去试另一个选择。

回溯的第一个要点：选择，它展开了一颗空间树。

2. 第二步思考，有什么约束

约束条件限制了当前的选项，这道题的约束条件是：

不能有前导0，截取的字符串不能比255大，字符串截取长度为1-3

我们应该利用这些约束条件，对其进行剪枝。

• 用这些约束进行充分地剪枝，去掉一些选择，避免搜索「不会产生正确答案」的分支。

3. 第三部思考，目标是什么
   什么时候应该收集结果
4. 定义dfs函数

return的作用是退回上一个选择点！！！

class Solution {
    List<String> res = new ArrayList<>();
    List<String> path = new ArrayList<>();
    int n;

    public List<String> restoreIpAddresses(String s) {
        n = s.length();
        dfs(s, 0);
        return res;
    }

    //我们第一步面临几个选择.
    // 1.选一个
    // 2.选两个
    // 3.选三个
    public void dfs(String s, int start) {
        if (start == n && path.size() == 4) {
            StringBuilder sb = new StringBuilder();
            for (String ss : path) {
                sb.append(ss);
                sb.append(".");
            }
            sb.deleteCharAt(sb.length() - 1);
            res.add(sb.toString());
            return;
        }
        
        //走到底，发现每一个选择都是合理，但整体选择就是错误的了
        //纵向剪枝
        //如：s：123454 path:[1,2,3,4]
        if (start < n && path.size() == 4) {
            return;
        }
        for (int len = 1; len <= 3; len++) {
            //删除不合法的前导0
            // len > 1 才会可能不合法： 01 022
            //横向剪辑
            if (len != 1 && s.charAt(start) == '0') {
                //return的作用是退回上一个选择点！！！
                return;
            }
            //保证后续s.substring() 合法
            if (start + len - 1 >= n) {
                return;
            }
            String t = s.substring(start, start + len);
            //截取后 大小不能超过255
            if (len == 3 && Integer.parseInt(t) > 255)
                return;
            path.add(t);
            dfs(s, start + len);
            path.remove(path.size() - 1);
        }

    }
}

比较版本号

思路：

1. 分格String，用split，得到string []s
2. 取两个str数组[] ，mark version
3. 将s里的值装成Integer比较

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] s1 = version1.split("\\.");
        String[] s2 = version2.split("\\.");
        int length = s1.length > s2.length ? s1.length : s2.length;
        String[] ss1 = new String[length];
        String[] ss2 = new String[length];
        for (int i = 0; i < s1.length; i++) {
            ss1[i] = s1[i];
            if (i == s1.length - 1) {
                i++;
                while (i < length) {
                    ss1[i] = "0";
                    i++;
                }
            }
        }
        for (int i = 0; i < length; i++) {
            ss2[i] = s2[i];
            if (i == s2.length - 1) {
                i++;
                while (i < length) {
                    ss2[i] = "0";
                    i++;
                }
            }
        }
        System.out.println(Arrays.toString(ss1));
        System.out.println(Arrays.toString(ss2));
        for (int i = 0; i < length; i++) {
            if (Integer.parseInt(ss1[i]) > Integer.parseInt(ss2[i])) {
                return 1;
            } else if (Integer.parseInt(ss1[i]) < Integer.parseInt(ss2[i])) {
                return -1;
            }
        }
        return 0;
    }
}

字节2面时候遇到过，不让用已知方法（java里String#split 方法），不让分割成String数组，可以试着自己手写一个双指针的方法

括号生成[137]

思路：

1. 先把树图给列举出来，思考选择（加右括号还是左括号），约束，目标
2. 回溯属性，path作为参数来说，return时只带恢复现场。而不是像全局属性一样（如下下），得手动恢复现场

class Solution {
    List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        dfs(0, 0, n, "");
        return res;
    }

    public void dfs(int lcnt, int rcnt, int n, String path) {
        if (lcnt + rcnt == 2 * n) {
            res.add(path.toString());
            return;
        }
        //") xxxx" 肯定不合法
        if (path.length() == 1 && path.charAt(0) == ')')
            return;
        //合法的括号，lcnt的大小肯定是得等于n
        if (lcnt < n) {
            // System.out.println("L");
            // System.out.println(path);
            dfs(lcnt + 1, rcnt, n, path + "(");
        }

        //只有当前位置： lcnt>rcnt,才可以加")"eg： ((() 
        if (rcnt < lcnt) {
            // System.out.println("R");
            // System.out.println(path);
            dfs(lcnt, rcnt + 1, n, path + ")");
        }

    }
}

全局属性path

class Solution {
    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    public List<String> generateParenthesis(int n) {
        dfs(0, 0, n);
        return res;
    }

    public void dfs(int lcnt, int rcnt, int n) {
        if (lcnt + rcnt == 2 * n) {
            res.add(sb.toString());
            return;
        }
        //合法的括号，lcnt的大小肯定是得等于n
        if (lcnt < n) {
            sb.append("(");
            dfs(lcnt + 1, rcnt, n);
            sb.deleteCharAt(sb.length()-1);
        }

        //只有当前位置： lcnt>rcnt,才可以加")"eg： ((() 
        if (rcnt < lcnt) {
            sb.append(")");
            dfs(lcnt, rcnt + 1, n);
            sb.deleteCharAt(sb.length()-1);
        }

    }
}

字符串转换整数 (atoi)

最长有效括号

思路：

1. 找到匹配括号的下标，然后存进一个LIst
2. 接下来就是转换成 寻找最长连续子序列
   1. 两种做法：排序后滑动窗口，时间复杂度O（NlogN）
   2. hashset，时间复杂度O（N）

class Solution {
    public int longestValidParentheses(String s) {
        List<Integer> indexList = new ArrayList<>();

        Stack<Integer> st = new Stack();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                st.add(i);
            }
            if (s.charAt(i) == ')' && st.size() != 0) {
                int index = st.pop();
                indexList.add(i);
                indexList.add(index);
            }
        }
        Collections.sort(indexList);
        int res = 0;
        int l = 0;
        int r = 1;
        //找出该数组的最长连续数列的长度
        for (; r < indexList.size(); r++) {
            if (indexList.get(r) != indexList.get(r-1) + 1) {
                l = r;
            }
            res = Math.max(res, r - l + 1);
        }
        return res;
    }
}

class Solution {
    public int longestValidParentheses(String s) {
        List<Integer> indexList = new ArrayList<>();

        Stack<Integer> st = new Stack();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                st.add(i);
            }
            if (s.charAt(i) == ')' && st.size() != 0) {
                int index = st.pop();
                indexList.add(i);
                indexList.add(index);
            }
        }
        Set<Integer> set = new HashSet<>(indexList);
        int res = 0;
        // int l = 0;
        // int r = 1;
        //找出该数组的最长连续数列的长度
        // for (; r < indexList.size(); r++) {
        //     if (indexList.get(r) != indexList.get(r-1) + 1) {
        //         l = r;
        //     }
        //     res = Math.max(res, r - l + 1);
        // }
        // return res;
        //最长连续子序列
        for(int x: set){
            if(set.contains(x-1)){
                continue;
            }
            int nextX = x+1;
            int cnt  = 1;
            while(set.contains(nextX)){
                nextX++;
                cnt++;
            }
            res = Math.max(res,cnt);
        }
        return res;
    }
}

字符串相乘[116]

思路：

1. 直接背诵，debug一遍也行

class Solution {
    public String multiply(String num1, String num2) {
        // 特殊情况：有一个数为0，结果直接是0
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }

        // 用数组保存结果，最大长度 = num1长度 + num2长度
        int[] res = new int[num1.length() + num2.length()];

        // 从后往前模拟竖式相乘
        for (int i = num1.length() - 1; i >= 0; i--) {
            int n1 = num1.charAt(i) - '0';
            for (int j = num2.length() - 1; j >= 0; j--) {
                int n2 = num2.charAt(j) - '0';

                // res[i+j+1] 存放当前位的结果（个位）
                int sum = res[i + j + 1] + n1 * n2;

                // 更新个位
                res[i + j + 1] = sum % 10;

                // 更新进位（加到前一位）
                res[i + j] += sum / 10;
            }
        }

        // 构建字符串结果，去掉最高位可能的0
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < res.length; i++) {
            if (i == 0 && res[i] == 0) continue; // 跳过前导0
            result.append(res[i]);
        }

        return result.toString();
    }
}

最小覆盖子串

题目：

思路：

class Solution {
    public String minWindow(String s, String t) {
        // 1. 构建目标字符表：统计 t 中每个字符需要的数量
        Map<Character, Integer> target = new HashMap<>();
        int cnt = 0; // 还差多少个字符没有被窗口覆盖
        for (char c : t.toCharArray()) {
            target.put(c, target.getOrDefault(c, 0) + 1);
            cnt++; // t 每有一个字符，就多需要一个
        }

        // 2. 定义滑动窗口的左右边界
        int l = 0;
        int r = 0;

        String res = "";              // 记录最终结果
        int size = Integer.MAX_VALUE; // 记录最小窗口大小

        // 3. 滑动右指针，扩大窗口
        for (; r < s.length(); r++) {
            char cr = s.charAt(r);

            // 如果右指针的字符不是目标字符，直接跳过
            if (!target.containsKey(cr)) {
                continue;
            }

            // 如果 cr 仍是需要的字符，就让 cnt--（缺少的字符数减少）
            if (target.get(cr) > 0) {
                cnt--;
            }

            // 把该字符的需求数减一（可能出现负数，表示“多出来的”）
            target.put(cr, target.get(cr) - 1);

            // 4. 当 cnt == 0 时，说明窗口已经包含了 t 的所有字符
            while (cnt == 0) {
                // 更新结果：若当前窗口更小，则替换
                if (size > r - l + 1) {
                    size = r - l + 1;
                    res = s.substring(l, r + 1);
                }

                // 5. 收缩左指针，尝试缩小窗口
                char lc = s.charAt(l);
                if (target.containsKey(lc)) {
                    // 把左边的字符“归还”给 target
                    target.put(lc, target.get(lc) + 1);
                    // 如果归还后需求量 > 0，说明窗口不再满足条件
                    if (target.get(lc) > 0) {
                        cnt++;
                    }
                }
                l++; // 左指针右移，缩小窗口
            }
        }
        return res;
    }
}

反转字符串中的单词

思路：

1. 先把所有单词挑出来
2. 然后翻转 String数组

class Solution {
    public String reverseWords(String s) {
        //把所有单词都挑出来
        List<String> ss = split(s);
        //System.out.println(ss);
        //翻转单词
        Collections.reverse(ss);

        StringBuilder sb = new StringBuilder();
        for (String v : ss) {
            sb.append(v);
            sb.append(" ");
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    public List<String> split(String s) {
        int r = 0;
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for (; r < s.length(); r++) {
            if (s.charAt(r) == ' ') {
                if (sb.length() > 0) {
                    res.add(sb.toString());
                    sb = new StringBuilder();
                }
                continue;
            } else {
                sb.append(s.charAt(r));
            }
        }
        //["the sky is blue"] 这种情况会导致blue没法加进去
        //所以最后得做兜底
        if (sb.length() > 0)
            res.add(sb.toString());

        return res;
    }
}

最长公共前缀

耻辱：快手日常侧开一面竟然脑子坏了

思路：

1.

class Solution {
    public String longestCommonPrefix(String[] strs) {
        boolean tag = true;
        String res = "";
        //以第一个str为基准
        for (int i = 0; i < strs[0].length(); i++) {
            String preStr = strs[0].substring(0, i + 1);
            //遍历剩余的子串
            for (int j = 1; j < strs.length; j++) {
                //是否以preStr为开头
                if (!strs[j].startsWith(preStr)) {
                    tag = false;
                }
            }
            //所有都为，更新结果
            if (tag) {
                res = preStr;
            }
        }
        return res;
    }
}

验证IP地址

思路：

1. 就是简单模拟
2. 学到的东西：Integer.parseInt(x,进制) 可指定进制
3. 可以学学正则表达式

class Solution {
    public String validIPAddress(String queryIP) {
        if (is4Or6(queryIP)) {
            String[] ip = queryIP.split("\\.");
            // String[] ip = queryIP.split("."); 错误的, "." 在正则表达式里是 任意字符的意思
            // System.out.println(queryIP);
            // System.out.println(Arrays.toString(ip));
            if(getCnt('.',queryIP) != 3){
                return "Neither";
            }
            if (ip.length != 4) {
                return "Neither";
            }
            for (String s : ip) {
                try {
                    if (s.length() > 1 && s.charAt(0) == '0') {
                        return "Neither";
                    }
                    if (Integer.parseInt(s,10) > 255) {
                        return "Neither";
                    }
                } catch (Exception e) {
                    return "Neither";
                }
            }
            return "IPv4";
        } else {
            String[] ip = queryIP.split(":");
            if(getCnt(':',queryIP) != 7){
                return "Neither";
            }
            if (ip.length != 8) {
                return "Neither";
            }
            for (String s : ip) {
                if (s.length() > 4) {
                    return "Neither";
                }
                try{
                    //转成16进制
                    Integer.parseInt(s,16);
                }catch(Exception e){
                    return "Neither";
                }
            }
            return "IPv6";
        }
    }

    public boolean is4Or6(String queryIP) {
        if (queryIP.contains(".")) {
            return true;
        } else
            return false;
    }

    public int getCnt(char ch,String str) {
        int count = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ch) {
                count++;
            }
        }
        return count;
    }
}

基本计算器 II[67]

思路：

class Solution {
    Map<Character,Integer> calOrderMap = new HashMap(){
        {
            put('+',1);
            put('-',1);
            put('/',2);
            put('*',2);
            //put();
        }
    };

    public int calculate(String s) {
        //替换掉空格
        s = s.replaceAll(" ", "");
        Deque<Integer> nums = new ArrayDeque<>();
        Deque<Character> ops = new ArrayDeque<>();
        //防止出现 -1 + 5 这种情况
        nums.addLast(0);
        System.out.println(s);
        char[] cs = s.toCharArray();
        int n = cs.length;
        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (isNumber(c)) {
                int number = 0;
                int numIndex = i;
                while (numIndex < n && isNumber(cs[numIndex])) {
                    numIndex++;
                }
                nums.addLast(Integer.parseInt(s.substring(i, numIndex)));
                i = numIndex - 1;
            }
            //遇到运算符了
            else {
                //防止出现 9 + - 1
                //将其装换成 9 + 0 - 1
                if (i > 0 && (cs[i - 1] == '-' || cs[i - 1] == '+')) {
                    nums.addLast(0);
                }
                //遇到新的运算符，先把stack里能计算的给计算了 eg：9+8-1
                while (!ops.isEmpty()) {

                    if (calOrderMap.get(ops.peekLast()) >= calOrderMap.get(c)) {
                        cal(nums, ops);
                    } else {
                        break;
                    }
                }
                ops.addLast(c);
            }
        }
        // 举例：
        // 2+3*4
        // 遍历完后，栈里的情况大概是：
        // nums = [2, 3, 4]
        // ops = ['+', '*']
        while (!ops.isEmpty())
            cal(nums, ops);
        return nums.peekLast();
    }

    public boolean isNumber(char c) {
        return Character.isDigit(c);
    }

    public void cal(Deque<Integer> nums, Deque<Character> ops) {
        if (nums.isEmpty() || nums.size() <= 1)
            return;
        if (ops.isEmpty())
            return;
        //注意顺序
        int b = nums.pollLast();
        int a = nums.pollLast();
        char op = ops.pollLast();
        int opRes = 0;
        switch (op) {
            case '-':
                opRes = a - b;
                break;
            case '+':
                opRes = a + b;
                break;
            case '/':
                opRes = a / b;
                break;
            case '*':
                opRes = a * b;
                break;
        }
        nums.addLast(opRes);
    }
}

完全版，应对所有情况，即完整的计算器

class Solution {
    Map<Character, Integer> opsOrderMap = new HashMap<>() {
        {
            put('-', 1);
            put('+', 1);
            put('*', 2);
            put('/', 2);
            put('%', 2);
            put('^', 3);
        }
    };

    public int calculate(String s) {
        //分为两个Stack
        //一个存操作，一个存数字
        Deque<Character> ops = new ArrayDeque();
        Deque<Integer> nums = new ArrayDeque();
        //为了防止第一个就是负数
        nums.addLast(0);

        //去掉全部空格
        s = s.replaceAll(" ", "");
        char[] cs = s.toCharArray();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (c == '(') {
                ops.addLast(c);
            } else if (c == ')') {
                //计算 ( ) 里的内容了
                while (!ops.isEmpty()) {
                    if (ops.peekLast() != '(') {
                        cal(nums, ops);
                    } else {
                        //为 ( 说明() 已经计算好了 弹出即可
                        ops.pollLast();
                        break;
                    }
                }
            } else {
                //转换数字
                if (isNumber(c)) {
                    // 19  char 转成 Integer
                    int number = 0;
                    int numIndex = i;
                    // while(numIndex < n&&isNumber(cs[numIndex])){
                    //     number = number*10 + (cs[numIndex] - '0');
                    //     numIndex++;
                    // }
                    while (numIndex < n && isNumber(cs[numIndex])) {
                        numIndex++;
                    }
                    nums.addLast(Integer.parseInt(s.substring(i, numIndex)));
                    i = numIndex - 1;
                } else {
                    // 1 - -2 → 1 - (0-2)
                    // 1 + +2 → 1 + (0+2)
                    // (+-3) → (0+0-3)
                    if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
                        nums.addLast(0);
                    }
                    // 有一个新操作入栈时，先把能算的给算了 eg： 1+7-9 -：当前新操作
                    while (!ops.isEmpty() && ops.peekLast() != '(') {
                        char prev = ops.peekLast();
                        if (opsOrderMap.get(prev) >= opsOrderMap.get(c)) {
                            cal(nums, ops);
                        } else {
                            //没有就继续遍历 eg: 12+9*1 当前运算符为 * 
                            break;
                        }
                    }
                    ops.addLast(c);
                }

            }

        }
        while (!ops.isEmpty()) {
            cal(nums, ops);
        }
        return nums.peekLast();
    }

    public void cal(Deque<Integer> nums, Deque<Character> ops) {
        if (nums.isEmpty()) {
            return;
        }
        if (ops.isEmpty()) {
            return;
        }
        int b = nums.pollLast();
        int a = nums.pollLast();
        char op = ops.pollLast();
        int res = 0;
        switch (op) {
            case '+':
                res = a + b;
                break;
            case '-':
                res = a - b;
                break;
            case '*':
                res = a * b;
                break;
            case '/':
                res = a / b;
                break;
            case '^':
                res = a ^ b;
                break;
            case '%':
                res = a % b;
                break;
        }
        nums.addLast(res);
    }

    public boolean isNumber(char c) {
        return Character.isDigit(c);
    }
}

解码方法[42]

思路：

1. dfs分隔
2. 但单单dfs，就超时了
3. 得进行记忆化操作

class Solution {
    int n;
    int res = 0;

    public int numDecodings(String s) {
        n = s.length();
        dfs(0, s);
        return res;
    }

    public void dfs(int startIndex, String s) {
        if (startIndex == n) {
            res++;
            return;
        }
        for (int i = 1; i <= 2; i++) {
            if (startIndex + i  > n) {
                return;
            }
            String s1 = s.substring(startIndex, startIndex + i);
            if (s1.charAt(0) == '0' && s1.length() >= 1) {
                return;
            }
            int num = Integer.parseInt(s1);
            if (num > 26) {
                return;
            }
            dfs(startIndex + i, s);

        }
    }
}

记忆化后

class Solution {
    int n;
    int res = 0;
    int[] memo; // 用于记忆化

    public int numDecodings(String s) {
        n = s.length();
        memo = new int[n];
        Arrays.fill(memo, -1); // -1 表示未计算
        dfs(0, s);
        return res;
    }

    public void dfs(int startIndex, String s) {
        if (startIndex == n) {
            res++;
            return;
        }

        // 如果当前索引的结果已经计算过，直接累加并返回
        if (memo[startIndex] != -1) {
            res += memo[startIndex];
            return;
        }

        int beforeRes = res; // 记录进入这个索引前的 res

        for (int i = 1; i <= 2; i++) {
            if (startIndex + i > n) return;

            String s1 = s.substring(startIndex, startIndex + i);
            if (s1.charAt(0) == '0') return; // 0 开头不合法

            int num = Integer.parseInt(s1);
            if (num < 1 || num > 26) {
                return;
            }
            dfs(startIndex + i, s);
        }

        // memo[startIndex] = 当前索引开始的新方案数
        memo[startIndex] = res - beforeRes;
    }
}

验证回文串

思路：

1. 熟悉几个API的使用
2. 双指针

class Solution {
    public boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while(i <= j){
            while(i < j && !Character.isLetterOrDigit(s.charAt(i))) i++;
            while(i < j && !Character.isLetterOrDigit(s.charAt(j))) j--;
            if(Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) return false;
            i++; j--;
        }
        return true;
    }
}

正则表达式匹配

有效的括号字符串

思路：

1. 双栈，存小标
2. 最后判断一下下标是否合法 eg：(* or *(

class Solution {
    public boolean checkValidString(String s) {
        Stack<Integer> left = new Stack();
        Stack<Integer> stars = new Stack();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                left.add(i);
            } else if (c == '*') {
                stars.add(i);
            } else {
                if (!left.isEmpty()) {
                    left.pop();
                } else if (!stars.isEmpty()) {
                    stars.pop();
                } else
                    return false;
            }

        }
        //eg：( *
        while(!stars.isEmpty() && !left.isEmpty()){
            if(stars.pop() < left.pop()){
                return false;
            }
        }
        return left.isEmpty();
    }
}

字母异位词分组[12]

思路：

1. 字符串字典排序，然后MAP

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String,List<String>> slots = new HashMap<>();
        for(String s: strs){
            char []cs = s.toCharArray();
            Arrays.sort(cs);
            String newS = new String(cs);
            if( slots.get(newS) == null){
                List<String>  list = new ArrayList<>();
                list.add(s);
                slots.put(newS,list);
            }
            else slots.get(newS).add(s);
        }
        return new ArrayList<>(slots.values()); 
    }
}

交错字符串[27]

题目：

思路：

1. dfs，困惑：有时候连dfs的函数都想不出来，真的逆天，没想清楚是字符串是怎么匹配的。还是得把回溯树给画出来
2. 回溯时间复杂度为2^k（k为s3的长度），故得进行记忆化，来剪枝

class Solution {
    int[][] cache;

    public boolean isInterleave(String s1, String s2, String s3) {
        int n1 = s1.length();
        int n2 = s2.length();
        int n3 = s3.length();
        if (n1 + n2 != n3) {
            return false;
        }
        cache = new int[n1][n2];
        //查找字符串里是否包含s1 但可断续
        return dfs(s1, s2, s3, 0, 0, 0);
    }

    public boolean dfs(String s1, String s2, String s3, int i, int j, int k) {
        if (i == s1.length() && j == s2.length() && k == s3.length()) {
            return true;
        }
        if (i + j > s3.length()) {
            cache[i][j]= -1;
            return false;
        }
        if (i < s1.length() && j < s2.length()) {
            if (cache[i][j] == -1) {
                return false;
            }
            if (cache[i][j] == 1) {
                return true;
            }
        }
        if (i < s1.length()) {
            if (s1.charAt(i) == s3.charAt(k) && dfs(s1, s2, s3, i + 1, j, k + 1)) {
                if (i < s1.length() && j < s2.length())
                    cache[i][j] = 1;
                return true;
            }
        }
        if (j < s2.length()) {

            if (s2.charAt(j) == s3.charAt(k) && dfs(s1, s2, s3, i, j + 1, k + 1)) {
                if (i < s1.length() && j < s2.length())
                    cache[i][j] = 1;
                return true;
            }
        }
        if (i < s1.length() && j < s2.length())
            cache[i][j] = -1;
        return false;
    }

    public boolean canForm(String t, StringBuilder sb) {
        int i = 0;
        int j = 0;
        while (j < t.length() && i < sb.length()) {
            if (t.charAt(j) == sb.charAt(i)) {
                j++;
                sb.setCharAt(i, '#');
            }
            i++;
        }
        return j == t.length();
    }
}

补充题9. 36进制加法

思路：就是大数相加的扩展

去除重复字母

字符串解码[90]

思路

1. 类似于 基本计算器，也是双栈
2. 一个栈存数字，一个栈存字符。这里的 [ 就类似于 *
3. 逻辑，遇到字符，遍历直到不是字符，遇到数字也是，遇到] 就 cal运算。

class Solution {
    public String decodeString(String s) {
        Stack<Integer> nums = new Stack();
        Stack<String> chars = new Stack();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int startIndex = i;
                while (startIndex < s.length() && Character.isDigit(s.charAt(startIndex))) {
                    startIndex++;
                }
                nums.add(Integer.parseInt(s.substring(i, startIndex)));
                i = startIndex - 1;
            } else if (c == ']') {
                cal(nums, chars);
            } else if (c == '[') {
                chars.add(c + "");
            } else {
                int startIndex = i;
                while (startIndex < s.length() && s.charAt(startIndex) >= 'a' && s.charAt(startIndex) <= 'z') {
                    startIndex++;
                }
                chars.add(s.substring(i, startIndex));
                i = startIndex - 1;
            }
        }
        //System.out.println(chars);

        StringBuilder res = new StringBuilder();
        List<String> list = new ArrayList();
        while (!chars.isEmpty()) {
            list.add(chars.pop());
        }
        for (int i = list.size() - 1; i >= 0; i--) {
            res.append(list.get(i));
        }
        return res.toString();
    }

    public void cal(Stack<Integer> nums, Stack<String> chars) {
        // 基础检查，如果栈为空则返回
        if (nums.isEmpty() || chars.isEmpty()) {
            return;
        }

        // 1. 获取重复因子
        int factor = nums.pop();

        // 2. 提取需要重复的字符串片段
        StringBuilder segment = new StringBuilder();
        while (!chars.isEmpty() && !chars.peek().equals("[")) {
            // 优化点 1: Pop and Prepend (弹出并前置)
            // 将弹出的片段插入到 StringBuilder 的开头 (index 0)
            // 这样可以避免额外的 List 存储和二次反转操作
            segment.insert(0, chars.pop());
        }

        // 3. 移除开头的左括号 '['
        if (!chars.isEmpty() && chars.peek().equals("[")) {
            chars.pop();
        }

        // 4. 重复片段并推回栈中
        String segmentStr = segment.toString();

        // 优化点 2: 使用 String.repeat() (推荐 Java 11+)
        String repeatedString = segmentStr.repeat(factor);

        chars.push(repeatedString);
    }
}

时间复杂度