题目描述(困难难度)

字符串匹配,? 匹配单个任意字符,* 匹配任意长度字符串,包括空串。和第 10 题有些类似。

解法一 动态规划

直接按照之前第 10 题,修改一下就可以了。

同样是用 dp[i][j] 表示所有的情况,然后一层一层的根据递推关系求出来。

public boolean isMatch(String text, String pattern) {
        // 多一维的空间,因为求 dp[len - 1][j] 的时候需要知道 dp[len][j] 的情况,
        // 多一维的话,就可以把 对 dp[len - 1][j] 也写进循环了
        boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
        // dp[len][len] 代表两个空串是否匹配了,"" 和 "" ,当然是 true 了。
        dp[text.length()][pattern.length()] = true;

        // 从 len 开始减少
        for (int i = text.length(); i >= 0; i--) {
            for (int j = pattern.length(); j >= 0; j--) {
                // dp[text.length()][pattern.length()] 已经进行了初始化
                if (i == text.length() && j == pattern.length())
                    continue;
                //相比之前增加了判断是否等于 * 
                boolean first_match = (i < text.length() && j < pattern.length() && (pattern.charAt(j) == text.charAt(i) || pattern.charAt(j) == '?' || pattern.charAt(j) == '*'));
                if (j < pattern.length() && pattern.charAt(j) == '*') {
                    //将 * 跳过 和将字符匹配一个并且 pattern 不变两种情况
                    dp[i][j] = dp[i][j + 1] || first_match && dp[i + 1][j];
                } else {
                    dp[i][j] = first_match && dp[i + 1][j + 1];
                }
            }
        }
        return dp[0][0];
    }

时间复杂度:text 长度是 T,pattern 长度是 P,那么就是 O(TP)。

空间复杂度:O(TP)。

同样的,和第10题一样,可以优化空间复杂度。

public boolean isMatch(String text, String pattern) {
    // 多一维的空间,因为求 dp[len - 1][j] 的时候需要知道 dp[len][j] 的情况,
    // 多一维的话,就可以把 对 dp[len - 1][j] 也写进循环了
    boolean[][] dp = new boolean[2][pattern.length() + 1];
    dp[text.length() % 2][pattern.length()] = true;

    // 从 len 开始减少
    for (int i = text.length(); i >= 0; i--) {
        for (int j = pattern.length(); j >= 0; j--) {
            if (i == text.length() && j == pattern.length())
                continue;
            boolean first_match = (i < text.length() && j < pattern.length() && (pattern.charAt(j) == text.charAt(i)
                                                                                 || pattern.charAt(j) == '?' || pattern.charAt(j) == '*'));
            if (j < pattern.length() && pattern.charAt(j) == '*') {
                dp[i % 2][j] = dp[i % 2][j + 1] || first_match && dp[(i + 1) % 2][j];
            } else {
                dp[i % 2][j] = first_match && dp[(i + 1) % 2][j + 1];
            }
        }
    }
    return dp[0][0];
}

时间复杂度:text 长度是 T,pattern 长度是 P,那么就是 O(TP)。

空间复杂度:O(P)。

解法二 迭代

参考这里,也比较好理解,利用两个指针进行遍历。

boolean isMatch(String str, String pattern) {
    int s = 0, p = 0, match = 0, starIdx = -1;     
    //遍历整个字符串
    while (s < str.length()){
        // 一对一匹配,两指针同时后移。
        if (p < pattern.length()  && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){
            s++;
            p++;
        }
        // 碰到 *,假设它匹配空串,并且用 startIdx 记录 * 的位置,记录当前字符串的位置,p 后移
        else if (p < pattern.length() && pattern.charAt(p) == '*'){
            starIdx = p;
            match = s;
            p++;
        }
        // 当前字符不匹配,并且也没有 *,回退
        // p 回到 * 的下一个位置
        // match 更新到下一个位置
        // s 回到更新后的 match 
        // 这步代表用 * 匹配了一个字符
        else if (starIdx != -1){
            p = starIdx + 1;
            match++;
            s = match;
        }
        //字符不匹配,也没有 *,返回 false
        else return false;
    }

    //将末尾多余的 * 直接匹配空串 例如 text = ab, pattern = a*******
    while (p < pattern.length() && pattern.charAt(p) == '*')
        p++;

    return p == pattern.length();
}

时间复杂度:如果 str 长度是 T,pattern 长度是 P,虽然只有一个 while 循环,但是 s 并不是每次都加 1,所以最坏的时候时间复杂度会达到 O(TP),例如 str = "bbbbbbbbbb",pattern = "*bbbb"。每次 pattern 到最后时,又会重新开始到开头。

空间复杂度:O(1)。

递归

第10题中还有递归的解法,但这题中如果按照第 10 题的递归的思路去解决,会导致超时,目前没想到怎么在第 10 题的基础上去改,有好的想法大家可以和我交流。

如果非要用递归的话,可以按照动态规划那个思路,先压栈,然后出栈过程其实就是动态规划那样了。所以其实不如直接动态规划。

动态规划的应用,理清递推的公式就可以。另外迭代的方法,也让人眼前一亮。

results matching ""

    No results matching ""