Wildcard Matching

galaxy_robot 发布于2019-08-14 17:19 / 2380人阅读

摘要：题目链接这道题还是可以用的方法，用的数组来解，空间复杂度较高。和不同，这道题的符号和前面的没有关系，不需要一起考虑。最坏的情况下，间隔出现且每个都要匹配很多字符，设一个平均匹配里面个字符，。其中，是的长度，是的长度。

Wildcard Matching

题目链接：
https://leetcode.com/problems...
这道题还是可以用"Regular Expression Matching" 的方法，用2d的dp数组来解，空间复杂度较高。

    public boolean isMatch(String s, String p) {
        /* boolean dp[len(s) + 1][len(p) + 1] 
         * dp[i+1][j+1] means if s[0, i] match p[0, j]
         * function: dp[i+1][j+1] 
         *         a. p[j] = * => 1. empty: dp[i+1][j]
         *                        2. one: dp[i][j]
         *                        3. multiple: dp[i][j+1]
         *         b. p[j] = s[i] | p[j] = ? => dp[i][j]
         * start: dp[0][0] = true, dp[0][j+1] = dp[0][j] & p[j] = *
         * result: dp[len(s)][len(p)]
         */
         
         boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
         // start
         dp[0][0] = true;
         for(int j = 0; j < p.length(); j++) dp[0][j+1] = dp[0][j] & (p.charAt(j) == "*");
         
         // loop
         for(int i = 0; i < s.length(); i++) {
             for(int j = 0; j < p.length(); j++) {
                 if(p.charAt(j) == "*") {
                     dp[i+1][j+1] = dp[i+1][j] | dp[i][j] | dp[i][j+1];
                 }
                 else if(p.charAt(j) == s.charAt(i) || p.charAt(j) == "?") dp[i+1][j+1] = dp[i][j];
             }
         }
         return dp[s.length()][p.length()];
    }

另一种思路是greedy，只需要O(1)的空间。和regular expression不同，这道题的star符号和前面的character没有关系，不需要一起考虑。而且star是可以匹配任何string的，"aa", "ab"都可以。所以check是否匹配的时候，只需要按位一个一个判断就行了。用两个指针i和j分别扫描s和p，loop过程中有以下几种情况：

成功匹配：s[i] == p[j] or p[j] == "?" => i++, j++

出现星号：p[j] == "*"

匹配不上：return false

第二种情况比较麻烦，多带带讨论一下。

p[j]匹配0个 => j++

p[j]匹配1个 => j++, i += 1

p[j]匹配2个 => j++, i += 2
......

可以看出来，要尝试不同的匹配个数，所以要加两个指针保存之前出现star时的i和j：stari和starj。那么每次碰到"*"的时候，都保存一下，先试下匹配0个的时候后面的字符是否可以匹配上，如果不行再试1个，2个。。重复这个过程。
以s的长度为loop的终点，所以最后还要考虑一下p后面还有多的"*"的情况。

时间复杂度度

最好的情况下，没有star或者所有star都匹配0个字符，O(M+N)。
最坏的情况下，star间隔出现且每个star都要匹配很多字符，设一个star平均匹配s里面x个字符，O(xN + M) = O(M*N)。其中，M是s的长度，N是p的长度。

    public boolean isMatch(String s, String p) {
        int i = 0, j = 0;
        int stari = -1, starj = -1;
        while(i < s.length()) {
            // 1. match
            if(j < p.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == "?")) {
                i++; j++;
            }
            // 2. star
            else if(j < p.length() && p.charAt(j) == "*") {
                // first match 0
                stari = i;
                starj = ++j;
            }
            // different number that "*" matches 
            else if(stari != -1) {
                // match number +1
                i = ++stari;
                j = starj;
            }
            // 3. not match and no star
            else return false;
        }
        // remove last "*" in p
        while(j < p.length() && p.charAt(j) == "*") j++;
        
        return j == p.length();
    }

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66562.html

leetcode-44. Wildcard Matching

摘要：正则由于的存在，所以有多种状态，中间状态储存都需要记录下来。然后以这些状态为动态的中转，继续判断到最后。最后正则匹配字符串是否成功的判断依据，就是正则字符串的最大，是否出现在遍历到最后的状态列表中。题目阐释：正则匹配字符串，用程序实现关键理解：正则匹配，动态规划思想，一个个向后追溯，后面的依赖前面的匹配成功。正则和待匹配的字符串长度不一，统一到正则字符串的index索引上，每...

leanxi 2019-07-30 17:20 评论0 收藏0
[Leetcode] Wildcard Matching 通配符匹配

摘要：当我们遇到一个时，因为之后可能要退回至该位置重新匹配，我们要将它的下标记录下来，比如。但是，当我们连续遇到两次的情况，如何保证我还是能继续匹配，而不是每次都退回导致循环呢所以我们还要记录一个，用来记录用上一个连续匹配到的中的下标。 Wildcard Matching Implement wildcard pattern matching with support for ? and ...

tainzhi 2019-08-14 12:35 评论0 收藏0
[LintCode/LeetCode] Wildcard Matching

摘要：递归和动规的方法没有研究，说一下较为直观的贪心算法。用和两个指针分别标记和进行比较的位置，当遍历完后，若也遍历完，说明完全配对。当之前出现过，且此时和完全无法配对的时候，就一起退回在和配对过的位置。再将和逐个加继续比较，并将后移。 Problem Implement wildcard pattern matching with support for ? and *. ? Matche...

Ethan815 2019-08-14 15:43 评论0 收藏0
LC44 wildcard matching

摘要：各一个指针，表示上一次真正到的位置。在的时候，上，增加下一步知道出界，发现是错误的所以需要回到上次的地方，即一旦走出去，无法返回，需要一个指针记录最后的地方。 public class Solution { public boolean isMatch(String s, String p) { int idxs = 0, idxp = 0, idxmatch ...

Tychio 2019-08-14 17:17 评论0 收藏0
Leetcode 44 Wildcard Matching 通配符匹配

摘要：难度题目给出一个字符串和一个要求我们给出这个字符串是否匹配这个其中通配符跟我们平常见到的一样是和代表任意单个字符代表一个或多个字符这个题跟简单正则匹配比较类似可以跟这里面第二个解法一样采取类似的动态规划解法在里取中间某个确定的字符串序列将字 Implement wildcard pattern matching with support for ? and *. ? Matches ...

SimonMa 2019-08-14 17:16 评论0 收藏0