Leetcode 字符串

Leetcode 字符串

indexOf-Leetcode 28

native string matching

public class StrStrLeetcode28 {
    static int strStr(String haystack, String needle) {
        char[] text = haystack.toCharArray();
        char[] pattern = needle.toCharArray();
        int n = text.length;
        int m = pattern.length;
        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (pattern[j] != text[i + j]) {
                    break;
                }
            }
            if (j == m) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(strStr("aaacaaab", "aaab"));
    }
}

kmp string matching

public class StrStrLeetcode28KMP {
    static int strStr(String haystack, String needle) {
        char[] text = haystack.toCharArray();
        char[] pattern = needle.toCharArray();
        int n = text.length;
        int m = pattern.length;
        int[] lps = lps(pattern);
        int i = 0;
        int j = 0;
        while ((n - i) >= (m - j)) {
            if (text[i] == pattern[j]) { // 匹配成功
                i++;
                j++;
            } else if (j != 0) { // 匹配失败
                j = lsp[j - 1];
            } else { // 匹配失败 j == 0
                i++;
            }
            if (j == m) { // 找到解
                return i - j;
            }
        }
        return -1;
    }

    static int[] lps(char[] pattern) {
        int[] lps = new int[pattern.length];
        int i = 1; // 后缀
        int j = 0; // 前缀 同时也是数量
        while (i < pattern.length) {
            if (pattern[i] == pattern[j]) {
                j++;
                lps[i] = j;
                i++;
            } else if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
        return lps;
    }

    public static void main(String[] args) {
        System.out.println(strStr("aaaaaaab", "aaab"));
//        System.out.println(Arrays.toString(prefix("aaab".toCharArray())));
        System.out.println(Arrays.toString(lsp("ababaca".toCharArray())));

    }
}

• 很多文章里[^17]，把 lps 数组的向后平移一位，lps 用 -1 填充，这个平移后的数组称为 next
  • 这样可以用 -1 代替 j == 0 的判断
  • 并可以在 j > 0 向前移动时，做少量优化（不用 next 数组也能做同样优化）
• 其它字符串匹配算法有：BM 算法、sunday 算法、Horspool 算法等

最长公共前缀-Leetcode 14

public class LCPLeetcode14 {
    static String longestCommonPrefix(String[] strings) {
        char[] first = strings[0].toCharArray();
        for (int i = 0; i < first.length; i++) {
            char ch = first[i];
            for (int j = 1; j < strings.length; j++) {
                if (i == strings[j].length() || ch != strings[j].charAt(i)) {
                    return new String(first, 0, i);
                }
            }
        }
        return strings[0];
    }

    public static void main(String[] args) {
        System.out.println(longestCommonPrefix(new String[]{"flower", "flow", "flight"})); // fl
        System.out.println(longestCommonPrefix(new String[]{"dog","racecar","car"})); //
        System.out.println(longestCommonPrefix(new String[]{"ab","a"})); // a
        System.out.println(longestCommonPrefix(new String[]{"dog","dogaa","dogbb"})); // dog
    }
}

最长回文子串-Leetcode 5

public class LongestPalindromeLeetcode5 {
    public static void main(String[] args) {
        System.out.println(longestPalindrome("babad"));  // bab
        System.out.println(longestPalindrome("cbbd"));	 // bb
        System.out.println(longestPalindrome("a"));		 // a
    }

    record Result(int i, int length) {
        static Result max(Result r1, Result r2, Result r3) {
            Result m = r1;
            if (r2.length > m.length) {
                m = r2;
            }
            if (r3.length > m.length) {
                m = r3;
            }
            return m;
        }
    }

    static String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        Result max = new Result(0, 1);
        for (int i = 0; i < chars.length - 1; i++) {
            Result r1 = extend(chars, i, i);
            Result r2 = extend(chars, i, i + 1);
            max = Result.max(max, r1, r2);
        }
        return new String(chars, max.i, max.length);
    }

    private static Result extend(char[] chars, int i, int j) {
        int len = chars.length;
        while (i >= 0 && j < len && chars[i] == chars[j]) {
            i--;
            j++;
        }
        i++;
        return new Result(i, j - i);
    }
}

• 还有时间复杂度更低的算法：Manacher

最小覆盖子串-Leetcode 76

public class MinWindowLeetcode76_2 {
    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC")); // BANC
        System.out.println(minWindow("aaabbbbbcdd", "abcdd")); // abbbbbcdd
    }

    record Answer(int count, int i, int j) {

    }

    static String minWindow(String s, String t) {
        char[] source = s.toCharArray();
        char[] target = t.toCharArray();
        int[] targetCountMap = new int[128];
        int[] windowCountMap = new int[128];
        for (char ch : target) {
            targetCountMap[ch]++;
        }
        int i = 0;
        int j = 0;
        Answer answer = new Answer(Integer.MAX_VALUE, i, j);
        int passCount = 0;
        for (int count : targetCountMap) {
            if (count > 0) {
                passCount++;
            }
        }
        int pass = 0;
        while (j < source.length) {
            char right = source[j];
            int c = ++windowCountMap[right];
            if (c == targetCountMap[right]) {
                pass++;
            }
            while (pass == passCount && i <= j) {
                if (j - i < answer.count) {
                    answer = new Answer(j - i, i, j);
                }
                char left = source[i];
                windowCountMap[left]--;
                if (windowCountMap[left] < targetCountMap[left]) {
                    pass--;
                }
                i++;
            }
            j++;
        }

        return answer.count != Integer.MAX_VALUE ? s.substring(answer.i, answer.j + 1) : "";
    }
}

Leetcode 单调队列和栈 Leetcode 设计