[leetcode] Wildcard Matching |unix那种wildcard matching

Posted by: lexigrey on: September 30, 2013

• In: leetcode
• 1 Comment

这个和regex的 .*不一样。这个是平时cd src*这种；?可以match任意一个字符，*可以match任意一个字符串，可以是空。

算法：下面这个算法超时，不过能写出来就不错了。每次两个字符串的第一个字母比较，若p的第一个字母是*，则一点点的chop s和p除了*剩下的recursive比较。p的那个*可以占用s的0个字符，1个字符，2个字符。。

一点优化：出现连续的*，取最右边那个就行。

public boolean isMatch(String s, String p) {
  if (s.length() == 0 && p.length() == 0)
    return true;
  if (p.length() == 0)
    return false;
  char c = p.charAt(0);
  if (s.length() != 0 && (c == '?' || c == s.charAt(0)))
    return isMatch(s.substring(1), p.substring(1));
  if (c == '*') {
    for (int i = 0; i <= s.length(); i++) { 
      // i is "* is taking up how many chars in s"
      String sLeft = "";
      if (s.length() != 0)
        sLeft = s.substring(i);
      if (isMatch(sLeft, p.substring(1)))
        return true;
     }
  }
  return false;
}

Tags: math