Is Word Pattern II easy or hard?

Word Pattern II is usually considered a medium-to-hard backtracking problem. The recursion itself is straightforward, but enforcing the bijection constraint while exploring substring partitions makes the implementation tricky during interviews.

Word Pattern II Python/Java solution

Most implementations use recursive backtracking with a hash map and a set. Python solutions typically use dictionaries and sets, while Java implementations rely on HashMap and HashSet. The algorithm structure remains the same: attempt substring assignments, validate mappings, and backtrack when mismatches occur.

How to solve Word Pattern II in O(n)?

An O(n) solution is not known for the general case because the algorithm must explore different substring assignments. The problem inherently requires trying combinations of substring partitions. Backtracking with pruning and hash maps is the most practical approach used in interviews and competitive solutions.

What is the best approach for Word Pattern II?

Backtracking with a hash map and a set (or bidirectional maps) is the standard approach. The algorithm assigns substrings to pattern characters while ensuring a bijection. Recursion explores candidate mappings and backtracks when mismatches occur. This solution runs in exponential time but is the expected interview approach.

Is Word Pattern II asked at Google/Amazon/Meta?

Word Pattern II is a classic backtracking interview problem and has appeared in coding interviews at companies that emphasize recursion and search problems. Variations of pattern-to-string mapping and bijection constraints are commonly discussed at companies like Google, Meta, and Amazon.

What data structure is used in Word Pattern II?

The core data structures are a hash map for mapping pattern characters to substrings and a set or reverse map to enforce the bijection constraint. These structures allow constant-time checks when validating mappings during recursion.

What is the time complexity of Word Pattern II?

The worst-case time complexity is exponential, typically expressed as O(n * m^n), where n is the pattern length and m is the string length. The algorithm tries multiple substring partitions for each pattern character. Space complexity is O(n) due to recursion depth and the mapping structures.

Description Solution Video 9:32

291. Word Pattern II

Medium49.1% acceptance6 companiesPremium elsewhere, free here

Given a pattern and a string s, return true if s matches the pattern.

A string s matches a pattern if there is some bijective mapping of single characters to non-empty strings such that if each character in pattern is replaced by the string it maps to, then the resulting string is s. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings.

Example 1:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

Example 2:

Input: pattern = "aaaa", s = "asdasdasdasd"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "asd"

Example 3:

Input: pattern = "aabb", s = "xyzabcxzyabc"
Output: false

Constraints:

1 <= pattern.length, s.length <= 20
pattern and s consist of only lowercase English letters.

Asked at 6 companies

Dropbox Uber Tiktok Apple Amazon Microsoft

Topics

9:32

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

291. Word Pattern II

Asked at 6 companies

Topics

Similar problems