Hidden in Order
EasyTwo Pointers
Problem
A puzzle hides a code word pattern inside a longer text: the letters of pattern appear in text in the same order, though not necessarily next to each other.
Return true if pattern can be obtained from text by deleting zero or more characters, and false otherwise.
Example 1
- Input:
- pattern = "ace", text = "abcde"
- Output:
- true
a, c and e appear in this order in 'abcde'.
Example 2
- Input:
- pattern = "aec", text = "abcde"
- Output:
- false
The only 'c' comes before the only 'e'.
Example 3
- Input:
- pattern = "", text = "xyz"
- Output:
- true
Constraints
- 0 ≤ pattern.length ≤ 10^5
- 0 ≤ text.length ≤ 10^5
- Both strings consist of lowercase English letters
Hint
Show the first hint
Match the first letter of pattern as early in text as you can. Can matching it later ever help?
Walkthrough
How to approach it
01Clarify before coding
- Must the letters be contiguous? No, only in the same relative order.
- Is an empty pattern hidden in any text? Yes, delete everything.
- Can letters repeat in pattern? Yes, each occurrence needs its own matching position in text.
02Brute force
Generate subsequences of text and compare each with pattern, or try every alignment recursively.
Cost: Exponential in the length of text: 2^n subsequences.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.