'?' 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]; } }
相关推荐
Wildcard Matching Wildcard Matching O(N) by Jimbowhy http://blog.csdn.net/WinsenJiansbomber/article/details/50862569 在 LeetCode 上看到第二个有趣的问题,是关于字符串匹配的,在接触过正则表达式后就...
简单的平台独立库,用于将字符串与通配符掩码进行比较。
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 ...
Examples of wildcard matching 26 Overview of the development provisioning process 27 Developing an App 30 Figure 4-1 Figure 4-2 Figure 4-3 Figure 4-4 The development process 30 The development process...
Wildcard Matching Longest Common Prefix Valid Number Integer to Roman Roman to Integer Count and Say Anagrams Valid Anagram Simplify Path Length of Last Word Isomorphic Strings Word Pattern 栈和队列 ...
wildcard matching 动态规划 longest common prefix , 简单 valid number, hard, 用有限自动机 integer to roman ,easy , 模拟 roman to integer ,easy , 模拟 count and say , easy , 模拟 Anagrams 字符串处理,map...
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是一个网站,人们——主要是软件工程师——练习他们的编码技能。 有 800 多个问题(并且还在不断...├── Wildcard Matching │ ├── Readme.md │ └── solution.js ├── Valid Number │
leetcode中国 买卖股票 从easy一直问到hard 数独 从medium的判断是不是valid ...Wildcard Matching 判断source string和pattern string是否match, ?代表任意一个字母,比如 s = "Happy" p = "H?pp?" 这种情况
leetcode 答案 算法心得 大纲 解算法 = 思路->思路验证->直译->结果验证 进步 = 解算法->看高手答案->临摹->形成后续TODO ...容易跑偏,要直译,要直译,要直译!...很多都是可以直接求出来的...No.44(wildcard matching) No
通配符匹配leetcode Greedy-5 Problem1: Wildcard Matching () Problem2: Bikes in a Campus ()
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-matchingpackage io.lcalmsky.leetcode. wildcard_matchingclass io.lcalmsky.leetcode. wildcard_matching.Solutiontest io.lcalmsky.leetcode. wildcard_matching.SolutionTest问题清
- 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 '...
通配符字符串匹配字符串匹配,其中一个字符串包含通配符( )
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...
- 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 '...
- 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 '...
- 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 'http:// code....