bugfree Icon
interview-course
interview-course
interview-course
interview-course
interview-course
interview-course
interview-course
interview-course

Leetcode Problem 291. Word Pattern II

291. Word Pattern II

Leetcode Solutions

Backtracking with Bijective Mapping

  1. Define a recursive function isMatch that takes the current index of s, the current index of pattern, the current mapping, and a set of already mapped strings.
  2. If both the pattern and s are fully matched, return true.
  3. If either the pattern or s is exhausted, return false.
  4. Retrieve the current pattern character.
  5. If the pattern character is already in the mapping, check if s starts with the mapped string at the current index. If it does, continue with the next characters.
  6. If the pattern character is not in the mapping, try to map it to every possible non-empty substring of s that starts at the current index and has not been mapped to another character.
  7. After each mapping, recursively call isMatch to continue with the next characters.
  8. If the recursive call returns true, the current mapping leads to a solution, so return true.
  9. If the mapping does not lead to a solution, backtrack by removing the current mapping and trying the next substring.
  10. If no mapping leads to a solution, return false.
UML Thumbnail

Iterative Deepening with Bijective Mapping

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...