Substring Matching Pattern

Easy
1775.

Substring Matching Pattern

Substring Matching Pattern is an easy coding problem on strings and string matching, asked in Google interviews.

You are given a string s and a pattern p that contains exactly one '*'.

The '*' may be replaced by any sequence of zero or more characters. Return true if p can be turned this way into a substring of s, and false otherwise. (A substring is a contiguous, possibly empty, run of characters.)

Example 1

Input
s = "leetcode", p = "ee*e"
Output
true
Explanation
Replacing '*' with "tcod" gives "eetcode", a substring of s.

Example 2

Input
s = "car", p = "c*v"
Output
false
Explanation
There is no 'v' in s at all.

Example 3

Input
s = "luck", p = "u*"
Output
true
Explanation
"u", "uc" and "uck" all match.

Constraints

  • 1 <= s.length <= 50
  • 1 <= p.length <= 50
  • s contains only lowercase English letters
  • p contains only lowercase English letters and exactly one '*'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var hasMatch = function(s, p) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Substring Matching Pattern — Solution in Python, Java & C++

Substring Matching Pattern solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Substring Matching Pattern is an easy coding problem on strings and string matching, asked in Google interviews.

  • Difficulty: Easy
  • Topics: Strings, String Matching
  • Asked at: Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a string s and a pattern p that contains exactly one '*'.

The '*' may be replaced by any sequence of zero or more characters. Return true if p can be turned this way into a substring of s, and false otherwise. (A substring is a contiguous, possibly empty, run of characters.)

Example 1

Input: s = "leetcode", p = "ee*e"
Output: true
Explanation: Replacing '*' with "tcod" gives "eetcode", a substring of s.

Example 2

Input: s = "car", p = "c*v"
Output: false
Explanation: There is no 'v' in s at all.

Example 3

Input: s = "luck", p = "u*"
Output: true
Explanation: "u", "uc" and "uck" all match.

Constraints

  • 1 <= s.length <= 50
  • 1 <= p.length <= 50
  • s contains only lowercase English letters
  • p contains only lowercase English letters and exactly one '*'

Hints for Substring Matching Pattern

  1. Hint 1

    Split p at the star into a prefix a and a suffix b. You need an occurrence of a followed, later and without overlap, by an occurrence of b.

  2. Hint 2

    Which occurrence of a gives b the most room?

  3. Hint 3

    Take the leftmost occurrence of a, then search for b starting right after it. Empty a or b always match.

How to solve Substring Matching Pattern

A match is a, then anything, then b, inside s. Choosing the earliest occurrence of a leaves the longest tail of s in which to find b, so a single greedy pair of searches decides it.

Approach

  1. Let a = p[0 .. star) and b = p[star + 1 ..].
  2. Find the first index i where a occurs in s; if there is none, return false.
  3. Return whether b occurs in s at some index >= i + a.length.

Why it works

If any match exists, with a at i' and b at j >= i' + |a|, then the leftmost occurrence i <= i' satisfies j >= i + |a| too, so the greedy search finds b as well. Conversely anything it finds is a valid match.

Complexity

  • Time — O(n * m)
  • Space — O(1)

Pitfalls

  • a and b must not overlap: in s = "ab", p = "ab*b" is false.
  • An empty side matches anywhere — some library calls (Swift's range(of:), PHP 7's strpos) mishandle an empty needle, so test it explicitly.

Reference solution

Python

def hasMatch(s: str, p: str) -> bool:
    star = p.index("*")
    a, b = p[:star], p[star + 1:]
    i = s.find(a)
    if i < 0:
        return False
    return s.find(b, i + len(a)) >= 0

Java

public static boolean hasMatch(String s, String p) {
    int star = p.indexOf('*');
    String a = p.substring(0, star), b = p.substring(star + 1);
    int i = s.indexOf(a);
    if (i < 0) return false;
    return s.indexOf(b, i + a.length()) >= 0;
}

C++

bool hasMatch(string s, string p) {
    size_t star = p.find('*');
    string a = p.substr(0, star), b = p.substr(star + 1);
    size_t i = s.find(a);
    if (i == string::npos) return false;
    return s.find(b, i + a.size()) != string::npos;
}

JavaScript

var hasMatch = function(s, p) {
    var star = p.indexOf("*");
    var a = p.substring(0, star), b = p.substring(star + 1);
    var i = s.indexOf(a);
    if (i < 0) return false;
    return s.indexOf(b, i + a.length) >= 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings