字符串匹配

匹配子串

10. 正则表达式匹配 hard

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

• '.' 匹配任意单个字符
  '.' Matches any single character.​​​​
• '*' 匹配零个或多个前面的那一个元素
  '*' Matches zero or more of the preceding element.

所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。
The matching should cover the entire input string (not partial).

此题可以通过动态规划或者有限状态自动机做, 但我选择调库

java

class Solution {
    public boolean isMatch(String s, String p) {
        return s.matches(p);
    }
}

go

func isMatch(s, p string) bool {
    res, _ := regexp.MatchString("^"+p+"$", s)
    return res
}

28. 找出字符串中第一个匹配项的下标 easy

给你两个字符串 haystack 和 needle，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1。
Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

经典的字符串单模匹配模型有很多, 如 Knuth-Morris-Pratt 算法、Boyer-Moore 算法、Sunda 算法等

解法 1 暴力

class Solution {
    public int strStr(String s1, String s2) {
        // 从尾部往前减m个, 再加1个
        for (int i = 0; i < s1.length() + 1 - s2.length(); i++) {
            if (check(s1, s2, i)) return i;
        }
        return -1;
    }

    private boolean check(String s1, String s2, int idx) {
        int i = idx, j = 0;
        for (; j < s2.length(); i++, j++) {
            if (s1.charAt(i) != s2.charAt(j)) return false;
        }
        return true;
    }
}

解法 2 KMP

KMP 算法的核心在于 pattern 前缀函数.
前缀函数 $\pi$ 可以用一个数组表示: π[i] = 当字符串 $S_{0-i}$ 的真前缀==真后缀时, 前后缀的长度最大值
通过前缀函数的性质可以求得回退的位置i=π[i-1], 因为当 i 失配时, i-1 还是匹配的
有两种思路可以解释函数 $\pi$ 如何 work:

第 1 种: 将 pattern+"#"+str, 然后求 π[i]>=len(pattern) 时的 i;
第 2 种: 不拼接 pattern 和 str, 搞 2 个指针 a 和 b, 分别从 pattern 和 str 的头部向后移动, 当 str[a],pattern[b]失配时, pattern[0:b-1]仍然是匹配的, 根据 π[b-1]能找到指针 b 回退的位置 b=π[b-1]; 直到 b=len(pattern)即可;
找到回退位置比较难理解, 现在只看 pattern, π[b-1]是长度, 如果当作索引的话, 就是真前缀的下一个位置; pattern[0:π[b-1]-1] == pattern[?:b-1], 所以 b 回退到 π[b-1]

现在, 只要知道如何求解前缀函数即可. 如何求解前缀函数呢?
有趣的是, 前缀函数的求解过程相当于自己匹配自己, 同时也是真前后缀的最大长度

从头到尾计算 pattern 的 π[i], pattern 的真后缀要从 pattern[1]开始; 搞 2 个指针 i 和 j, 初始指向 i->pattern[1] 开始迭代 i;
让 j=π(i-1), 此时 pattern[0:j-1]==pattern[i-1-(j-1):i-1], 如果 pattern[j]==pattern[i], 则 i,j 同时前进并更新π(i);
如果 pattern[j]!=pattern[i], 则 j 需要回退尝试用别的子串匹配, j=π[j-1], 直到 pattern[j]==pattern[i] 匹配上;

这里不用判断子串是不是最长的, 因为 j 从后往前回退, 后缀序列固定, 一定越来越短

java

class Solution {
    public int strStr(String haystack, String needle) {
        char[] ptn = needle.toCharArray();
        char[] str = haystack.toCharArray();
        int n = str.length;
        int m = ptn.length;
        int[] pi = new int[m];
        for (int i = 1; i < m; i++) {
            int j = pi[i - 1]; // 开始比对的位置, 也是已经匹配的长度
            while (j > 0 && ptn[i] != ptn[j]) j = pi[j - 1];
            if (ptn[i] == ptn[j]) j++;
            pi[i] = j;
        }
        int i = 0, j = 0;
        for (; j < m && i < n; i++) {
            while (j > 0 && ptn[j] != str[i]) j = pi[j - 1];
            if (ptn[j] == str[i]) j++;
        }
        if (j == m) return i - j; // i是子串的下一个位置, 减j正好是0位
        return -1;
    }
}

go

func strStr(str string, ptn string) int {
    pi := make([]int, len(ptn))
    for i := 1; i < len(ptn); i++ {
        j := pi[i-1]
        for j > 0 && ptn[j] != ptn[i] {
            j = pi[j-1]
        }
        if ptn[j] == ptn[i] {
            j++
        }
        pi[i] = j
    }
    i, j := 0, 0
    for ; i < len(str) && j < len(ptn); i++ {
        for j > 0 && ptn[j] != str[i] {
            j = pi[j-1]
        }
        if ptn[j] == str[i] {
            j++
        }
    }
    if j == len(ptn) {
        return i - j
    }
    return -1
}

python

class Solution:
    def strStr(self, haystack: str, ptn: str) -> int:
        pi = [0] * len(ptn)
        for i in range(1, len(ptn)):
            j = pi[i - 1]
            while j > 0 and ptn[i] != ptn[j]:
                j = pi[j - 1]
            if ptn[i] == ptn[j]:
                j += 1
            pi[i] = j

        i, j = 0, 0
        while i < len(haystack) and j < len(ptn):
            while j > 0 and haystack[i] != ptn[j]:
                j = pi[j - 1]
            if haystack[i] == ptn[j]:
                j += 1
            i += 1

        if j == len(ptn):
            return i - j

        return -1

676.实现一个魔法字典 mid

LCR 064. 实现一个魔法字典

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。

实现 MagicDictionary 类：

• MagicDictionary() 初始化对象
• void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
• bool search(String searchWord) 给定一个字符串 searchWord, 判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true; 否则，返回 false.

可以暴力, 也可以字典树+dfs

解法 1 暴力

每次判定的时间复杂度，$O(len(dict)\ast len(word))$

class MagicDictionary {
    private String[] dict;

    public void buildDict(String[] dictionary) {
        this.dict = dictionary;
    }

    public boolean search(String searchWord) {
        for (String s : dict) {
            if (check(s, searchWord)) return true;
        }
        return false;
    }

    private boolean check(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        int n = s1.length();
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (s1.charAt(i) != s2.charAt(i)) cnt++;
            if (cnt > 1) return false;
        }
        return cnt == 1;
    }
}

解法 2 字典树+回溯

将某个位置当 root 开始回溯
建树时间复杂度，$O(sum(dict))$
每次判定的时间复杂度，$O(len(word))$

class MagicDictionary {

    private final Node root = new Node();

    private static class Node {
        Node[] table = new Node[26];
        boolean isLeaf;
    }

    private void insert(String word) {
        Node n = root;
        for (char c : word.toCharArray()) {
            if (n.table[c - 'a'] == null)
                n.table[c - 'a'] = new Node();
            n = n.table[c - 'a'];
        }
        n.isLeaf = true;
    }

    public void buildDict(String[] dictionary) {
        for (String s : dictionary) {
            insert(s);
        }
    }

    public boolean search(String searchWord) {
        return backtracking(root, false, searchWord, 0);
    }

    private boolean backtracking(Node root, boolean used, final String word, int idx) {
        // 最后1个元素必须是leaf, 并且改过1个字母
        if (idx == word.length()) return used && root.isLeaf;
        for (int i = 0; i < 26; i++) {
            Node child = root.table[i];
            if (child != null) {
                if (used && word.charAt(idx) - 'a' != i) continue; // 没次数了
                if (backtracking(child, used || word.charAt(idx) - 'a' != i, word, idx + 1)) return true;
            }
        }
        return false;
    }
}

820. 单词的压缩编码 mid

单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：

• words.length == indices.length
• 助记字符串 s 以 '#' 字符结尾
• 对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 '#' 字符结束（但不包括 '#'）的 子字符串 恰好与 words[i] 相等

给你一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。

将所有单词塞进助记字符串, 单词中的子串可以共用尾部

• word 倒序建树
• 考虑新 word 能否覆盖或被覆盖
• 覆盖则减去之前的长度, 加新 word 长度
• 被覆盖当没有

class Solution {
    static class Node {
        Node[] table = new Node[26];
        boolean isLeaf;
    }

    public int minimumLengthEncoding(String[] words) {
        Node root = new Node();
        int res = 0;
        for (String s : words) {
            Node p = root;
            int add = 1 + s.length();
            boolean isNew = false;
            for (int i = s.length() - 1; i >= 0; i--) {
                int idx = s.charAt(i) - 'a';
                if (p.table[idx] == null) {
                    p.table[idx] = new Node();
                    isNew = true;
                } else if (p.table[idx].isLeaf) {
                    p.table[idx].isLeaf = false;
                    add -= 1 + s.length() - i;
                }
                p = p.table[idx];
            }
            if (isNew) p.isLeaf = true;
            res += isNew ? add : 0;
        }
        return res;
    }
}

回文判定

125. 验证回文串 easy

LCR 018. 验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true；否则，返回 false。

class Solution {
    public boolean isPalindrome(String s) {
        char[] arr = s.toCharArray();
        int l = 0, r = arr.length - 1;
        while (l < r) {
            char cl = arr[l];
            char cr = arr[r];
            if (!Character.isLetterOrDigit(cl)) {
                l++;
                continue;
            }
            if (!Character.isLetterOrDigit(cl)) {
                r--;
                continue;
            }
            if (Character.toLowerCase(cl) != Character.toLowerCase(cr)) return false;
            l++;
            r--;
        }
        return true;
    }
}

680. 验证回文字符串 Ⅱ easy

LCR 019. 验证回文串 II

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

class Solution {
    public boolean validPalindrome(String s) {
        return validPalindrome(s, 0, s.length() - 1, false);
    }

    private boolean validPalindrome(String s, int i, int j, boolean edited) {
        for (; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                if (edited) return false;
                return validPalindrome(s, i + 1, j, true) || validPalindrome(s, i, j - 1, true);
            }
        }
        return true;
    }
}

同构

205. 同构字符串 easy

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

要映射 2 次, 防止 1 对多和多对 1

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;
        Character[] m1 = new Character[128];
        Character[] m2 = new Character[128];
        for (int i = 0; i < s.length(); i++) {
            Character c1 = s.charAt(i);
            Character c2 = t.charAt(i);
            Character c3 = m1[c1]; // c3 == c2
            Character c4 = m2[c2]; // c4 == c1
            if (c3 == null && c4 == null) {
                m1[c1] = c2;
                m2[c2] = c1;
            }
            else if (!(c1.equals(c4) && c2.equals(c3))) return false;
        }
        return true;
    }
}