Wildcard Matching
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).
思路：
动态规划
我的代码：
public class Solution { /** * @param s: A string * @param p: A string includes "?" and "*" * @return: A boolean */ public boolean isMatch(String s, String p) { // write your code here if((s==null || s.length()==0) && (p==null || p.length()==0)) return true; if(s==null || s.length()==0) return false; if(p==null || p.length()==0) return false; int row = p.length(); int col = s.length(); boolean[][] isValid = new boolean[row][col]; if(p.charAt(0) == '*') { for(int j=0; j<col; j++) { isValid[0][j] = true; } } if(p.charAt(0)==s.charAt(0) || p.charAt(0)=='?') isValid[0][0] = true; boolean first = true; for(int i=0; i<row; i++) { if(p.charAt(i)==s.charAt(0) || p.charAt(i)=='?') { if(first) { isValid[i][0] = i==0?true:isValid[i-1][0]; first = false; } } else if(p.charAt(i) == '*') { if(i==0) isValid[i][0] = true; else isValid[i][0] = isValid[i-1][0]; } } for(int i=1; i<row; i++) { for(int j=1; j<col; j++) { if(p.charAt(i)=='*') { if(isValid[i-1][j] || isValid[i][j-1]) isValid[i][j] = true; } if(p.charAt(i)==s.charAt(j) || p.charAt(i)=='?') { if(isValid[i-1][j-1]) isValid[i][j] = true; } } } return isValid[row-1][col-1]; } }
我的代码2：
public class Solution { public boolean isMatch(String s, String p) { if((s==null || s.length()==0) && (p==null || p.length()==0)) return true; int n = s.length(); int m = p.length(); int count = 0; for (int i = 0; i < m; i++) { if (p.charAt(i) == '*') count++; } if (count==0 && m != n) return false; else if (m - count > n) return false; boolean[] isValid = new boolean[n+1]; isValid[0] = true; for(int i=0; i<m; i++) { if(p.charAt(i) == '*') { for(int j=0; j<n; j++) isValid[j+1] |= isValid[j]; } else { for(int j=n-1; j>=0; j--) { isValid[j+1] = ((p.charAt(i)=='?' || p.charAt(i)==s.charAt(j)) && isValid[j]); } isValid[0] = false; } } return isValid[n]; } }