Check If String Is a Prefix of Array

Check If String Is a Prefix of Array

What is this problem about?

In the "Check If String Is a Prefix of Array" coding problem, you are given a string s and an array of strings words. You need to determine if s is a prefix of the concatenation of the words in the array. Crucially, the string s must be exactly equal to the concatenation of some prefix of the array (i.e., the first $k$ words), not just a substring of the total concatenated string.

Why is this asked in interviews?

Uber and other ride-sharing apps use this to test basic logic and string handling efficiency. It's a test of whether you can solve a problem without using unnecessary memory. A naive solution might concatenate all words into a giant string and then check, but that's inefficient. It tests your ability to iterate through two data structures simultaneously.

Algorithmic pattern used

The pattern is Two Pointers or simple String Simulation. You iterate through the words array, keeping track of your progress in string s. You compare each word to the current segment of s. If they match, you move forward in s. If at any point the words don't match, or you finish string s in the middle of a word, it's not a valid prefix.

Example explanation

$s = "applepie"$, $words = ["apple", "pie", "cherry"]$

1. First word is "apple". It matches the start of s. Remaining s: "pie".
2. Next word is "pie". It matches the rest of s. Remaining s: "".
3. We have matched all of s using the first two full words. Result: True.

If $s = "applep"$, $words = ["apple", "pie"]$

1. "apple" matches. Remaining s: "p".
2. Next word is "pie". "pie" is not "p", and we finished s before finishing the word "pie". Result: False.

Common mistakes candidates make

The most common mistake is returning true if s is just a prefix of the entire concatenated string (e.g., if s is "applepi" and words are ["apple", "pie"], some might say true). The rule is that s must be the result of concatenating a whole number of words. Another mistake is creating a new concatenated string, which uses $O(N)$ extra space, rather than just comparing in place.

Interview preparation tip

Practice comparing strings using pointers or indices. Avoiding the creation of new objects (like concatenating strings) is a key optimization that interviewers look for in "Easy" and "Medium" string problems.