💬 字符串常见算法问题

• String to Integer (atoi)
• Convert a string to an integer.

• Longest Common Subsequence (LCS):
• Find the length of the longest common subsequence between two strings.

• Palindrome Check(判断回文字符串):
• Determine if a given string is a palindrome (reads the same backward as forward).

• Longest Palindromic Substring(最长回文子串):
• Find the longest substring that is a palindrome in a given string.

• Reverse a String(反转字符串):
• Reverse the characters in a string.
• eg: Reverse "hello" to "olleh".

• String Matching (字符串匹配):
• Substring Search. Find the occurrence of a substring within a string.

• Anagram Detection(字谜检测):
• Determine if two strings are anagrams (contain the same characters with the same frequency).

• String Compression(字符串压缩):
• Compress a string by counting repeated characters (e.g., "aaabbb" becomes "a3b3").

• Regular Expression Matching(实现正则表达式匹配):
• e.g. Implement regular expression matching with support for '.' and '*'.

• Others
• e.g. RollingHash, KMP

• 字符串和Array有很高的相似性

• 考察其他算法或者数据结构的载体

👣 字符串基本操作

String s = "hello world";
int l = s.length();
// l: 11;
int i = s.indexOf('e');
// i: 1
char c = s.charAt(4);
// c: 'o'
String sub = s.substring(6, 11);
// s: "world"
char[] arr = s.toCharArray();
// arr: ['h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', '.']
String[] arr2 = s.split(" ");
// arr2: "hello"	"world."
"   hello world".trim()
// "hello world"

👍 解答思路

• 确认题意和边界条件

• 和出题人沟通思路

• Coding（ 注意code style）

• 测试 - 常见case 和 边界case

• 分析复杂度

• 优化，follow up question

🥊 算法实战

LeetCode 344. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示：

* 1 <= s.length <= 105
s[i] 都是 ASCII 码表中的可打印字符

确定题意和边界条件

• 输入是什么？ 输出是什么？

• 具体计算过程应该什么样？

• 考虑边界情况？

• 是否有额外要求？ 是否引入库函数？

和出题人沟通思路

• 逐个确定疑问点

• 假装经过思考

• 提出优化方案的时候，一定要分析利弊

解1：反转字符串 一 额外空间解

解2：反转字符串-双指针

class Solution {
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length - 1;
        while(l < r) {
            char temp = s[l];
            s[l] = s[r];
            s[r] = temp;
            l++;
            r--;
        }
    }
}

💪🏻 Coding

• 注意沟通

• 注意 Code Style 有意义的函数和变量命名，合理的封装抽象

• 注意 代码逻辑清晰

• 注意有余力的情况下合理添加注释

• 注意边界

👣 测试

• 如果提供的有例子可以先测提供的例子

• 白板测试，可以口头测试，边写、边讲、边测。

👣 简单测试后-边界和Corner Case

• 一般情况正确之后考虑Corner Case ，null，“a”

优化和follow up

• 分析时间复杂度
• 分析复杂度之前，首先定义数据规模
• 分块分析，平行块只取最大

• 空间复杂度
• 不考虑输入和输出的额外空间
• 更优的时间复杂度，空间复杂度

• 更简洁的实现

• Trade off?

LeetCode 541. 反转字符串 II

解1：

class Solution {
    public String reverseStr(String s, int k) {
        char[] a = s.toCharArray();
        int start = 0;
        int end = a.length - 1;

        for (int i=0; i<a.length; i+=2*k) {
            reverseStrItem(a, i, Math.min(i+k-1, end));
        }

        return new String(a);
    }

    public void reverseStrItem(char[] arr, int start, int end) {
        while(start < end) {
            char temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            
            start += 1;
            end -= 1;
        }
    }
}

LeetCode1768. 交替合并字符串

解1：

class Solution {
    public String mergeAlternately(String word1, String word2) {
        int w1 = word1.length();
        int w2 = word2.length();
        int index = 0;
        char[] arr = new char[w1+w2];

        for (int i=0; i < w1 | i < w2; i++) {
            if (i < w1) arr[index++] = word1.charAt(i);
            if (i < w2) arr[index++] = word2.charAt(i);
        };

        return new String(arr);
    };
}

Leetcode5. 最长回文(palindromic)子串(substring)

解1：中心扩散

1. 遍历字符串中的每个位置，扩散指真head、tail，直到head, tail节点值不相等或者指真溢出，停止扩散。
1. 取当前节点作为中心位置



b. 取当前节点+右节点作为中心位置：

2. 扩散指真head、tail同时计算以

class Solution {
    public String longestPalindrome(String s) {
        int start = 0;
        int distance = 1;

        for (int i=0; i<s.length()-1; i++) {
            int m1 = getPalindrome(s, i, i);
            int m2 = getPalindrome(s, i, i+1);
            int maxDis = Math.max(m1, m2);
            if (maxDis > distance) {
                start = i;
                distance = maxDis;
            }
        }

        int offset = distance % 2 == 1 ? 1 : 2;
        start = start - (distance - offset) / 2;
        return s.substring(start, start + distance);
    }

    public int getPalindrome(String s, int head, int tail) {
        while(head > -1 && tail < s.length() && s.charAt(head) == s.charAt(tail)) {
            head--;//-1
            tail++;//3
        }

        return tail - head + 1 - 2;
    }
}

解2：动态规划

1. 长度>2

1. 长度=2

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2)
            return s;
        boolean[][] dp = new boolean[len][len];
        int l=0;
        int r=0;
        for (int i=0; i<len; i++) {
            dp[i][i] = true;
        }
        char[] charArray = s.toCharArray();
        for (int L=2; L<=len; L++) {
            for (int i=0; i<=len-L; i++) {
                int j = i + L - 1;
                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else if (j-i<3) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i+1][j-1];
                }
                if (dp[i][j] == true && j-i > r-l) {
                    l=i;
                    r=j;
                }   
            }
        }
        return s.substring(l, r+1);
    }
}