[LintCode/LeetCode] Wildcard Matching

Ethan815 发布于2019-08-14 15:43 / 3161人阅读

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

Problem

Implement wildcard pattern matching with support for "?" and "*".

"?" Matches any single character.
"*" Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).

Example

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

Note

递归和动规的方法没有研究，说一下较为直观的贪心算法。

用cs和cp两个指针分别标记s和p进行比较的位置，当cs遍历完s后，若cp也遍历完p，说明完全配对。

我们看一下while循环里的几个分支：

第一个if语句，若cp和cs指向的字符相等，或cp指向的字符为"?"，则说明这一位配对成功，两个指针继续前移；

第二个else if语句，当cp指向的字符为"*"，则后面字符的配对结果要受到影响，必须用star和match分别在p和s的当前位置，也就是cp和cs，进行标记。然后，cp前移，cs不动，为什么呢？因为，如果此时cp == p.length()，就已经可以结束while循环了；但若cp不是末位，那么p剩下的字符还要继续判断，至于cs，完全可以等到下一次成功配对字符后再移动；

第三个else if语句，这里最为费解。当p之前出现过star，且此时cp和cs完全无法配对的时候，就一起退回在star和match配对过的位置。再将cp和cs逐个加1继续比较，并将match后移。为什么star不用后移呢？因为star是大BOSS，可以任意和后面match走过的很多位配对下去呀；

最后一个else语句，返回false。但是这个false包含了哪些情况呢？其实，就是p中没有star且无法配对的情况。

再用一个while循环跳过p尾部的所有"*"，如果有的话。
最后，若cp走完p，说明完全配对。

Solution

Greedy

public class Solution {
    public boolean isMatch(String s, String p) {
        int cs = 0, cp = 0, star = -1, match = 0;
        while (cs < s.length()) {
            if (cp < p.length() && (p.charAt(cp) == s.charAt(cs) || p.charAt(cp) == "?")) {
                cs++;
                cp++;
            }
            else if (cp < p.length() && p.charAt(cp) == "*") {
                star = cp;
                match = cs;
                cp++;
            }
            else if (star != -1) {
                cp = star + 1;
                cs = match + 1;
                match++;
            }
            else return false;
        }
        while (cp < p.length() && p.charAt(cp) == "*") cp++;
        return cp == p.length();
    }
}

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) return false;
        int lens = s.length();
        int lenp = p.length();
        boolean[][] dp = new boolean[lens + 1][lenp + 1];
        boolean flag = false;
        for (int i = 0; i <= lens; i++) {
            flag = false;
            for (int j = 0; j <= lenp; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                    flag = true;
                    continue;
                }
                if (j == 0) {
                    dp[i][j] = false;
                    continue;
                }
                if (i == 0) dp[i][j] = dp[i][j - 1] && p.charAt(j - 1) == "*";
                else dp[i][j] = (matchChar(s.charAt(i - 1), p.charAt(j - 1)) && dp[i - 1][j - 1]) 
                                || (p.charAt(j - 1) == "*" && (dp[i][j - 1] || dp[i - 1][j]));    
                if (dp[i][j]) flag = true;
                if (dp[i][j] && p.charAt(j - 1) == "*" && j == lenp) return true;
            }
            if (!flag) return false;
        }
        return dp[lens][lenp];
    }
    public static boolean matchChar(char c, char p) {
        return (p == "?" || p == c);
    }
}

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

转载请注明本文地址：https://www.ucloud.cn/yun/65965.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
Wildcard Matching

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

galaxy_robot 2019-08-14 17:19 评论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