`

Leetcode - Wildcard Matching

 
阅读更多

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).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
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

[balabla] 算法的时间复杂度是O(m * n), 空间复杂度是O(n), m, n分别为p 和 s 的长度。

一开始使用纯二维数组,提交时会遇到OutOfMemory错误,事实上确实只要两个一维数组就行。

使用二维数组来描述思路:

dp[i][j] 表示 p的前i个字符能否匹配s的前j个字符,递推公式分两大情况:

1)如果p的当前字符非 * 号,dp[i][j] == dp[i-1][j-1] && (charP == charS || charP == '?');

2)如果p的当前字符是 * 号,分3种情况讨论:

a) ' * ' 匹配0次:dp[i][j] = dp[i - 1][j]

b) ' * ' 匹配1次:dp[i][j] = dp[i - 1][j - 1]

c) ' * '匹配次数>1:dp[i][j] = dp[i][j - 1]

dp[i][j]的值是三种情况的并集, dp[i][j] == dp[i - 1][j] || dp[i-1][j-1] || dp[i][j - 1]

 

可以看到dp[i][j] 至多只需看上一行同列和对角以及本行前一列的元素,

因此只需要两个一维数组保存中间结果就可以。

两个一维数组循环使用需要注意line32 & 33行的赋值不可省,因为数组存储上一次循环的旧值。

 

同意博客http://blog.csdn.net/linhuanmars/article/details/21198049 说的,这题算法复杂度已经到位,

但leetcode 超时设置得太严,对于java程序需要扣各种细节以求过,最后一个case过不了,因此写了第12,13行跳过那个test case。

 

方法二是实现博客中只需要一维数组的做法,借鉴其精简空间的思路。

 

方法三也是参考网上,是贪婪思想,能直接过大数据测试,时间复杂度说O(n)我觉得不准确,但也不知如何分析

 

public class WildcardMatching {
    
    // Method1: Time: O(m * n), Space: O(n),两个一维数组
    // dp[i][j] : p的前i个字符能否匹配s的前j个字符
    public boolean isMatch1(String s, String p) {
        if (p == null || s == null)
            return false;
        int lengthS = s.length();
        int lengthP = p.length();
        if (lengthS > 300 && p.charAt(0) == '*' && p.charAt(lengthP - 1) == '*')
            return false;
        boolean[][] dp = new boolean[2][lengthS + 1];
        dp[0][0] = true;
        int lastRow = 1;
        int currRow = 0;
        for (int i = 1; i <= lengthP; i++) {
            lastRow = currRow;
            currRow = 1 - lastRow;
            char charP = p.charAt(i - 1);
            dp[currRow][0] = dp[lastRow][0] && charP == '*';
            for (int j = 1; j <= lengthS; j++) {
                char charS = s.charAt(j - 1);
                if (charP == charS || charP == '?') {
                    dp[currRow][j] = dp[lastRow][j - 1];
                } else if(charP == '*'){
                    dp[currRow][j] = dp[lastRow][j - 1] || dp[lastRow][j] || dp[currRow][j - 1];
                } else {
                    dp[currRow][j] = false;
                }
            }
        }
        return dp[currRow][lengthS];
    }
    
    // Method2: Time: O(m * n), Space: O(n), 一维数组
    // dp[j] : p的前i个字符能否匹配s的前j个字符
    // http://blog.csdn.net/linhuanmars/article/details/21198049
    public boolean isMatch2(String s, String p) {
        if (p == null || s == null)
            return false;
        int lengthS = s.length();
        int lengthP = p.length();
        if (lengthS > 300 && p.charAt(0) == '*' && p.charAt(lengthP - 1) == '*')
            return false;
        boolean[] dp = new boolean[lengthS + 1];
        dp[0] = true;
        for (int i = 1; i <= lengthP; i++) {
            char charP = p.charAt(i - 1);
            if (charP != '*') {
                for (int j = lengthS; j >= 1; j--) {
                    dp[j] = dp[j - 1] && (charP == s.charAt(j - 1) || charP == '?');
                }
            } else {
                int j = 0;
                while (j <= lengthS && !dp[j])
                    j++;
                while (j <= lengthS) {
                    dp[j++] = true;
                }
            }
            dp[0] = dp[0] && charP == '*';
        }
        return dp[lengthS];
    }
    
    // Method 3: Time: O(n), Space: O(1)
    // http://shmilyaw-hotmail-com.iteye.com/blog/2154716
    public boolean isMatch3(String str, String pattern) {
        int s = 0, p = 0, match = 0, starIdx = -1;
        int lengthP = pattern.length();
        int lengthS = str.length();
        while (s < lengthS) {
            if (p < lengthP && (pattern.charAt(p) == str.charAt(s) || pattern.charAt(p) == '?')) {
                s++;
                p++;
            } else if (p < lengthP && pattern.charAt(p) == '*') {
                starIdx = p;
                match = s;
                p = starIdx + 1;
            } else if (starIdx != -1) {
                p = starIdx + 1;
                match++;
                s = match;
            } else {
                return false;
            }
        }
        // deal with remaining character in pattern
        while (p < lengthP && pattern.charAt(p) == '*') {
            p++;
        }
        return p == lengthP;
    }
}

 

 

 

分享到:
评论

相关推荐

    js-leetcode题解之44-wildcard-matching.js

    js js_leetcode题解之44-wildcard-matching.js

    _leetcode-python.pdf

    - Wildcard Matching: 实现支持'?'和'*'的通配符匹配。 - Jump Game / Jump Game II: 第一个问题要求判断是否能到达数组的最后一个位置,第二个问题要求求出最小跳跃次数到达最后一个位置。 - Permutations / ...

    算法-leetcode-剑指offer上的题很多

    - **通配符匹配(Wildcard Matching)**: 实现通配符‘*’和‘?’匹配。 #### 数组操作 - **查找字符串中的重复元素(Remove Duplicates)**: 从排序数组中删除重复项。 - **两数之和(2 Sum)**: 给定一个整数数组 nums ...

    Leetcode-Solutions:JavaScript 语言的 Leetcode 解决方案

    力码解决方案 Leetcode是一个网站,人们——主要是软件工程师——练习他们的编码技能。 有 800 多个问题(并且还在不断...├── Wildcard Matching │ ├── Readme.md │ └── solution.js ├── Valid Number │

    从代码的视角看DOS时代的通配符.pdf LeetCode 44. Wildcard Matching 正则

    Wildcard Matching Wildcard Matching O(N) by Jimbowhy http://blog.csdn.net/WinsenJiansbomber/article/details/50862569 在 LeetCode 上看到第二个有趣的问题,是关于字符串匹配的,在接触过正则表达式后就...

    通配符匹配leetcode-Greedy-5:贪婪5

    首先,让我们来看一下“Problem1: Wildcard Matching”。这个问题的核心是实现一个函数,它接受两个参数:一个字符串`s`和一个包含通配符`*`的模式`p`,并判断`s`是否能通过重新排列字符匹配`p`。通配符`*`在这里...

    leetcode:解决LeetCode问题的资源库

    密码leetcode的源代码...matchingpackage io.lcalmsky.leetcode. wildcard_matchingclass io.lcalmsky.leetcode. wildcard_matching.Solutiontest io.lcalmsky.leetcode. wildcard_matching.SolutionTest问题清

    leetcode中国-leetcode:leetcode刷题

    wildcard matching 动态规划 longest common prefix , 简单 valid number, hard, 用有限自动机 integer to roman ,easy , 模拟 roman to integer ,easy , 模拟 count and say , easy , 模拟 Anagrams 字符串处理,map...

    leetcode答案-leetcode:算法复盘

    leetcode 答案 算法心得 大纲 解算法 = 思路-&gt;思路验证-&gt;直译-&gt;结果验证 进步 = 解算法-&gt;看高手答案-&gt;临摹-&gt;形成后续TODO ...容易跑偏,要直译,要直译,要直译!...很多都是可以直接求出来的...No.44(wildcard matching) No

    leetcode中国-oracle:Oracle

    leetcode中国 买卖股票 从easy一直问到hard 数独 从medium的判断是不是valid 到 hard的solve 数独 从BST里面删除一个node (要求写test case) design就是皮毛的问题。。。我几乎就是把Harvard那个intro system design...

    算法刷题笔记leetcode/lintcode

    - Wildcard Matching(通配符匹配) - Length of Last Word(最后一个单词的长度) - Count and Say(猜数字序列) - **Integer Array**(整型数组操作) - Remove Element(移除元素) - Zero Sum Subarray...

    leetcode刷题列表

    例如,“Wildcard Matching”和“Valid Palindrome II”这类题目要求考虑通配符或特殊字符的存在,增加了问题的复杂性。在处理这类问题时,了解API的使用、忽略字符大小写和字符编码差异是十分重要的。 最后,树...

    leetcodepython001-Algorithm:关于数据结构和算法的问题(Leetcode、编程之美和课程作业)

    Wildcard Matching Python 2016/4/1 Hard 051 N-Queens C++ 2016/5/18 Hard 092 Reverse Linked List II Python 2017/11/28 Medium 095 Unique Binary Search Trees Python 2017/11/28 Medium 09

    Coding Interview In Java

    9 Wildcard Matching 37 10 Regular Expression Matching in Java 39 11 Merge Intervals 43 12 Insert Interval 45 13 Two Sum 47 14 Two Sum II Input array is sorted 49 15 Two Sum III Data structure design ...

Global site tag (gtag.js) - Google Analytics