Lexi's Leetcode solutions

[leetcode] Wildcard Matching |unix那种wildcard matching

Posted on: September 30, 2013

这个和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:

1 Response to "[leetcode] Wildcard Matching |unix那种wildcard matching"

可不可以用i,j来指向p和s的当前比较的position.然后避免使用substring呢。

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: