Check If String Is a Prefix of Array — Problem & Solution
Check If String Is a Prefix of Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Check If String Is a Prefix of Array is an easy coding problem on arrays and strings, asked in Amazon, TCS and Wipro interviews.
- Difficulty: Easy
- Topics: Arrays, Strings
- Asked at: Amazon, TCS, Wipro
- 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
A string s is a prefix string of words if it equals the concatenation of the first k entries of words for some k with 1 <= k <= words.length.
Return true if s is a prefix string of words.
Example 1
Input: s = "codekairo", words = ["code","kairo","rocks"]
Output: true
Explanation: The first two words concatenate to exactly s.
Example 2
Input: s = "codek", words = ["code","kairo"]
Output: false
Explanation: One word gives "code" and two give "codekairo" — neither is "codek".
Example 3
Input: s = "a", words = ["a","b"]
Output: true
Constraints
1 <= words.length <= 1001 <= words[i].length <= 201 <= s.length <= 1000All strings consist of lowercase English letters.
Hints for Check If String Is a Prefix of Array
Hint 1
Build the concatenation word by word and compare after each step.
Hint 2
Stop as soon as the built string is at least as long as
s— going further can only overshoot.Hint 3
Equality has to be exact; a prefix match is not enough.
How to solve Check If String Is a Prefix of Array
There are only words.length candidate concatenations, and they grow monotonically, so build them one word at a time and test for equality after each addition.
Approach
- Keep a growing buffer, initially empty.
- Append each word in order; after each append compare the buffer with
s. - Return
trueon an exact match; returnfalseonce the buffer is at least as long asswithout matching.
Why it works
Every candidate is a prefix of the next, so lengths increase strictly. Once the buffer reaches s.length without matching, no later candidate can match either, which makes the early exit safe.
Complexity
- Time —
O(n) where n is the total length of the words examined - Space —
O(n)
Pitfalls
- Using
s.startsWith(buffer)tests the wrong direction — the statement asks for equality. - Forgetting to stop makes the buffer grow past
sand wastes work on a decided answer.
Reference solution
Python
from typing import List
def isPrefixString(s: str, words: List[str]) -> bool:
built = ""
for w in words:
built += w
if built == s:
return True
if len(built) >= len(s):
return False
return FalseJava
public static boolean isPrefixString(String s, String[] words) {
StringBuilder built = new StringBuilder();
for (String w : words) {
built.append(w);
if (built.length() == s.length() && built.toString().equals(s)) return true;
if (built.length() >= s.length()) return false;
}
return false;
}C++
bool isPrefixString(string s, vector<string>& words) {
string built;
for (const string& w : words) {
built += w;
if (built == s) return true;
if (built.size() >= s.size()) return false;
}
return false;
}JavaScript
var isPrefixString = function(s, words) {
var built = "";
for (var i = 0; i < words.length; i++) {
built += words[i];
if (built === s) return true;
if (built.length >= s.length) return false;
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.