Skip to content

3407. Substring Matching Pattern

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
 public:
  bool hasMatch(const string& s, const string& p) {
    const int starPos = p.find('*');
    const string prefix = p.substr(0, starPos);
    const string suffix = p.substr(starPos + 1);
    const int i = s.find(prefix);
    return i != string::npos &&
           s.find(suffix, i + prefix.size()) != string::npos;
  }
};

1
2
3
4
5
6
7
8
9
class Solution {
  public boolean hasMatch(String s, String p) {
    final int starPos = p.indexOf('*');
    final String prefix = p.substring(0, starPos);
    final String suffix = p.substring(starPos + 1);
    final int i = s.indexOf(prefix);
    return i != -1 && s.indexOf(suffix, i + prefix.length()) != -1;
  }
}

1
2
3
4
5
class Solution:
  def hasMatch(self, s: str, p: str) -> bool:
    prefix, suffix = p.split('*')
    i = s.find(prefix)
    return i != -1 and s.find(suffix, i + len(prefix)) != -1