字符串的常见算法总结

1、无重复字符的最长子串

3. 无重复字符的最长子串
滑动窗口解题。设置一个map来存储字符与其出现的位置，再定义窗口的开始与结束指针。

public static int lengthOfLongestSubstring(String s) {
    //边界检查
    if (s == null || s.isEmpty()) {
        return 0;
    }
    //结果
    int res = 0;
    //定义一个map，key存放不重复的字符，val为字符的位置
    Map<Character, Integer> map = new HashMap<>();
    for (int start = 0, end = 0; end < s.length(); end++) {
        char c = s.charAt(end);
        if (map.containsKey(c)) {
            start = Math.max(map.get(c), start);
        }
        res = Math.max(end - start + 1, res);
        map.put(c, end + 1);
    }
    return res;
}

2、最长公共子序列

1143. 最长公共子序列
涉及到两个字符串求子序列的问题，一般都是动态规划的范畴。难点就是要找到状态转换方程。
定义一个二维数组 dp 用来存储最长公共子序列的长度，其中 dp[i][j] 表示 S1 的前 i 个字符与 S2 的前 j 个字符最长公共子序列的长度。考虑 S1i 与 S2j 值是否相等，分为下面两种情况:
参考这个！！

  public static int longestCommonSubsequence(String text1, String text2) {
    //边界检查
    if (text1 == null || text1.isEmpty()) {
        return 0;
    }
    if (text2 == null || text2.isEmpty()) {
        return 0;
    }
    int n1 = text1.length(), n2 = text2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];
    //状态转移方程
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    return dp[n1][n2];
}

3、最长重复子数组

718. 最长重复子数组
动态规划问题：

public static int findLength(int[] A, int[] B) {
    //边界检查
    if (A.length <= 0 || B.length <= 0) {
        return 0;
    }
    int result = 0;
    int n = A.length;
    int m = B.length;
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (A[i - 1] == B[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                result = Math.max(result, dp[i][j]);
            }
        }
    }
    return result;
}

4、字符串反转

使用两个指针。

public static void reverseString(char[] s) {
    //边界检查
    if (s.length <= 1) {
        return;
    }
    //双指针法
    int left = 0, right = s.length - 1;
    while (left < right) {
        char tmp = s[left];
        s[left++] = s[right];
        s[right--] = tmp;
    }
}

5、字符串能否由字典中单词组成

给定一个字符串s和一个字典dict，判断字符串能否有字典中的字符串组成，字典中的字符串可以出现多次。例如s=“Ilovebytedance”,dict={“I”,“love”,“bytedance”}
用动态规划，dp[i]表示字符串s[0~i]是否可分的bool值。
字节跳动单词拼接
 139. 单词拆分
参考这里！！！
也是动态规划问题：

 public static boolean wordBreak(String s, List<String> wordDict) {
    Set<String> wordDictSet = new HashSet(wordDict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length()];
}