LC44 wildcard matching

Tychio 发布于2019-08-14 17:17 / 3045人阅读

摘要：各一个指针，表示上一次真正到的位置。在的时候，上，增加下一步知道出界，发现是错误的所以需要回到上次的地方，即一旦走出去，无法返回，需要一个指针记录最后的地方。

public class Solution {
    public boolean isMatch(String s, String p) {
        int idxs = 0, idxp = 0, idxmatch = 0, idxstar = -1;
        // s, p 各一个指针，   idxmatch表示s上一次真正match到的位置。
        // abgefg             *g
        // 在idxs = 2的时候，match上，idxs增加
        // 下一步知道p出界，发现是错误的match, 所以需要回到上次match的地方，即idxmatch
        
        // ab    ?*b
        // aab   ?*b
        // bab   b*b
        
        while(idxs < s.length()){
            if(idxp< p.length() && (p.charAt(idxp) == "?" || s.charAt(idxs) == p.charAt(idxp)) ) {
                idxs++;                 // idxs一旦走出去，无法返回，需要一个指针记录最后match的地方。
                idxp++;                 // match错误，idxp可以由idxstar+1重新得到
            } else if(idxp< p.length() && (p.charAt(idxp) == "*")) {
                idxmatch = idxs;        // 开始match的地方，idxs之前的必须完全match
                idxstar = idxp;         // 记录*的位置
                idxp++;                 // 尝试match 0 个，即idxs不动，idxp往后移
            } else if(idxstar != -1) {  // 上次match错误，或者match不够
                idxmatch++;             // idxmatch唯一标记上次match的地方 
                idxs = idxmatch;        // match
                idxp = idxstar + 1;     // 一次match一个
            } else {
                return false;
            }
        }
        
        while(idxp< p.length() && p.charAt(idxp) == "*") {  // trailing "*"s
            idxp++;
        }
        
        return idxp == p.length();
        
    }
}

public class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] match=new boolean[s.length()+1][p.length()+1];
        match[s.length()][p.length()]=true;
        for(int i=p.length()-1;i>=0;i--){
            if(p.charAt(i)!="*")
                break;
            else
                match[s.length()][i]=true;
        }
        for(int i=s.length()-1;i>=0;i--){
            for(int j=p.length()-1;j>=0;j--){
                if(s.charAt(i)==p.charAt(j)||p.charAt(j)=="?")
                        match[i][j]=match[i+1][j+1];
                else if(p.charAt(j)=="*")
                        // i+1, j 表示j维持原位置，i向后一位，"*"  match with s.charAt(i)
                        // i, j+1 表示i维持原位置，j向后一位，"*" match with ""(empty)
                        match[i][j]=match[i+1][j]||match[i][j+1];
                else
                    match[i][j]=false;
            }
        }
        return match[0][0];
    }
}

海外云主机 GPU服务器 Wildcard LC lc域名 V44

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

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

leetcode-44. Wildcard Matching

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

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

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

SimonMa 2019-08-14 17:16 评论0 收藏0
[LintCode/LeetCode] Wildcard Matching

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

Ethan815 2019-08-14 15:43 评论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