`

Wildcard Matching

 
阅读更多
'?' 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

   我原来的想法,是通过一个二维数组,boolean matrix[i][j] 表示p中前i个元素与s中前j个元素的匹配情况

   无奈,TLE

   ===

 

 //摘自DISCUSS中的方法 :

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        int count = 0;
 // 计算p中'*'的个数
        for (int i = 0; i < n; i++) {
            if (p.charAt(i) == '*') count++;
        }
        if (count==0 && m != n) return false;
        else if (n - count > m) return false;
// 这个数组表示的是字符串s中,前i个元素的匹配情况
        boolean[] match = new boolean[m+1];
        match[0] = true;
        for (int i = 0; i < m; i++) {
            match[i+1] = false;
        }
// 他这种方法,原本应当用一个二维矩阵来存值的,但是实际上我们用到的只有它的上一层,所以,这里只用
// 一个一维的数组来存值即可
        for (int i = 0; i < n; i++) { // row
            if (p.charAt(i) == '*') {
                for (int j = 0; j < m; j++) { // col
  // 如果s中前j个个都匹配,那么自然*与第j+1个元素匹配,如果j+1元素都匹配,那么'*'就匹配空字符
                    match[j+1] = match[j] || match[j+1]; 
                }
            } else {
//对于!= '*'的元素 为什么要从后往前了, 因为考虑到前面的可能可能被之前的元素匹配了啊!!
                for (int j = m-1; j >= 0; j--) { // 从后往前
// match[j]代表的是前j个元素是否已经匹配,如果false,那么这里匹配也没用
                    match[j+1] = (p.charAt(i) == '?' || p.charAt(i) == s.charAt(j)) && match[j];                 
		 }
                match[0] = false;
            }
        }
        return match[m];
    }
}

 

分享到:
评论

相关推荐

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

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

    Wildcard Matching Functions Library-开源

    标题中的“Wildcard Matching Functions Library-开源”指的是一个专门用于处理字符串和通配符匹配的开源库。这个库可能包含了各种函数,旨在帮助开发者在不同平台上实现字符串与通配符模式的有效比较,例如“*”...

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

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

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

    squish test

    3. **Object Stability:** The tool supports wildcard matching of object names, allowing for changes between builds without the need to edit every script. This feature is crucial for maintaining the ...

    leetcode刷题列表

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

    Coding Interview in Java

    12. 字符串匹配问题:如Wildcard Matching(通配符匹配)、Flip Game(翻转游戏)等,这些题目要求熟悉字符串处理以及递归回溯等算法。 13. 字符串处理高级问题:如Scramble String(错乱字符串),验证字符串的...

    算法刷题笔记leetcode/lintcode

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

    _leetcode-python.pdf

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

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

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

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

    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

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

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

    leetcode中国-oracle:Oracle

    leetcode中国 买卖股票 从easy一直问到hard 数独 从medium的判断是不是valid ...Wildcard Matching 判断source string和pattern string是否match, ?代表任意一个字母,比如 s = "Happy" p = "H?pp?" 这种情况

    leetcode答案-leetcode:算法复盘

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

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

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

    解决:dubbo找不到dubbo.xsd报错

    - cvc-complex-type.2.4.c: The matching wildcard is strict, but no declaration can be found for element 'dubbo:application'. - schema_reference.4: Failed to read schema document '...

    wildcard-named:一个小巧易用的实用程序模块,用于使用JavaScript的已命名和未命名通配符来匹配字符串

    import wildcard from "wildcard-named" ; 基本例子 import wildcard from "wildcard-named" ; wildcard ( "//blog.com/page/14" , "//blog.com/page/[digit:page]" ) ; // { 'page': '14' } wildcard ( "abc-123:d2...

    wildcard-string-matching:字符串匹配,其中一个字符串包含通配符 (http

    本话题将深入探讨“wildcard-string-matching”,即带有通配符的字符串匹配问题,主要以Java语言为实现背景。 通配符通常用于表示一个或多个字符,常见的通配符有星号(*)和问号(?)。在字符串匹配中,星号代表零...

Global site tag (gtag.js) - Google Analytics