Check If String Is a Prefix of Array solution and explanation
9 more videos on this problem
Check If String Is a Prefix of Array| LeetCode 1961| EnglishCodeClips with Abhishek Ranjan · 10:58 · 567 views
1961. Check If String Is a Prefix of Array (Leetcode Easy)Programming Live with Larry · 4:38 · 510 views
LeetCode 1961 Check If String Is a Prefix of ArrayAlgorithmicIQ · 2:28 · 490 views
1961. Check If String Is a Prefix of Array - Daily Leetcode (Day 68)yeetcode · 2:48 · 272 views
Check If String Is a Prefix of Array | Leetcode 1961 | Approach + Code with explanation.Pirai's Academy · 5:21 · 191 views
CODING GENIE - CHECK IF STRING IS A PREFIX OF ARRAY - PYTHON - LEETCODEVAKSARA™ · 9:31 · 140 views
1961. Check If String Is a Prefix of Array with python | leetcode with python #leetcode #pythonArsalan Ahmed · 3:55 · 139 views
1961 Check If String Is a Prefix of ArrayTexas Tim . dev · 22:04 · 56 views
Check If String Is a Prefix of Array | Leetcode 1961 Telugu | Concatenation, Two-Pointer | srkcodesSrk Codes · 6:59 · 56 views
Check if a String is a prefix of a Array Leetcode weekly contest 253CodeinDepth · 4:01 · 298 views
The problem
Given a string s and an array of strings words, determine whether s is a prefix string of words.
A string s is a prefix string of words if s can be made by concatenating the first k strings in words for some positive k no larger than words.length.
Return true if s is a prefix string of words, or false otherwise.
Example 1:
Input: s = "iloveleetcode", words = ["i","love","leetcode","apples"] Output: true Explanation: s can be made by concatenating "i", "love", and "leetcode" together.
Example 2:
Input: s = "iloveleetcode", words = ["apples","i","love","leetcode"] Output: false Explanation: It is impossible to make s using a prefix of arr.
Constraints:
1 <= words.length <= 1001 <= words[i].length <= 201 <= s.length <= 1000words[i]andsconsist of only lowercase English letters.
Approach overview
Problem Overview: You receive a string s and an array of strings words. The task is to check whether s equals the prefix formed by concatenating the first few elements of words. Concatenation must start from index 0 and stop once the built string either matches s or exceeds it.
Approach 1: Iterative Concatenation (O(n) time, O(n) space)
Build a running string by concatenating elements from words one by one. After each append, compare the built string with s. If it equals s, return true. If the length exceeds s, the prefix cannot match, so return false. The algorithm scans each character once overall, giving O(n) time where n is the total number of characters processed. The extra space comes from storing the temporary concatenated string.
This approach is straightforward and easy to reason about. It mirrors the definition of the problem: build the prefix and check if it matches. However, repeated string concatenation can allocate new memory depending on the language runtime.
Approach 2: Prefix Matching With Removal (O(n) time, O(1) space)
Instead of building a new string, match characters directly from s while iterating through words. Maintain an index pointer inside s. For each word, compare its characters with the corresponding characters in s. If a mismatch occurs, return false. If the pointer reaches the end of s exactly after processing part or all of a word, return true.
This method avoids creating intermediate strings and processes characters in-place. The pointer effectively simulates removing matched prefixes from s. Each character is visited once, resulting in O(n) time and O(1) extra space.
This approach resembles a typical pointer traversal pattern used in two pointers problems. You iterate through the array of words while scanning the string sequentially.
Recommended for interviews: Prefix Matching With Removal is usually preferred. It demonstrates careful pointer control and avoids unnecessary allocations. Iterative concatenation still shows correct reasoning and is perfectly acceptable for an easy problem, but interviewers generally expect the constant-space pointer-based solution.
Approach 1: Iterative Concatenation
This approach involves iteratively concatenating the words in the array and checking if at any point this concatenated string equals the given string s or becomes a prefix of it. Keep concatenating until the concatenated string size becomes larger than s, at which point you conclude that s cannot be constructed from these prefixes.
def is_prefix_string(s, words):
concat = ''
for word in words:
concat += word
if concat == s:
return True
if len(concat) > len(s):
return False
return False
s = "iloveleetcode"
words = ["i", "love", "leetcode", "apples"]
print(is_prefix_string(s, words))public class Solution {
public boolean isPrefixString(String s, String[] words) {
StringBuilder concat = new StringBuilder();
for (String word : words) {
concat.append(word);
if (concat.toString().equals(s)) return true;
if (concat.length() > s.length()) return false;
}
return false;
}
public static void main(String[] args) {
Solution sol = new Solution();
String[] words = {"i", "love", "leetcode", "apples"};
System.out.println(sol.isPrefixString("iloveleetcode", words));
}
}#include <iostream>
#include <vector>
using namespace std;
bool isPrefixString(string s, vector<string>& words) {
string concat = "";
for (string word : words) {
concat += word;
if (concat == s) return true;
if (concat.length() > s.length()) return false;
}
return false;
}
int main() {
vector<string> words = {"i", "love", "leetcode", "apples"};
string s = "iloveleetcode";
cout << (isPrefixString(s, words) ? "true" : "false") << endl;
return 0;
}function isPrefixString(s, words) {
let concat = '';
for (let word of words) {
concat += word;
if (concat === s) return true;
if (concat.length > s.length) return false;
}
return false;
}
const s = "iloveleetcode";
const words = ["i", "love", "leetcode", "apples"];
console.log(isPrefixString(s, words));#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool isPrefixString(char *s, char **words, int wordsSize) {
char concat[1001] = "";
for (int i = 0; i < wordsSize; i++) {
strcat(concat, words[i]);
if (strcmp(concat, s) == 0) return true;
if (strlen(concat) > strlen(s)) return false;
}
return false;
}
int main() {
char *words[] = {"i", "love", "leetcode", "apples"};
char *s = "iloveleetcode";
printf("%s\n", isPrefixString(s, words, 4) ? "true" : "false");
return 0;
}using System;
public class Solution {
public bool IsPrefixString(string s, string[] words) {
string concat = string.Empty;
foreach (string word in words) {
concat += word;
if (concat == s) return true;
if (concat.Length > s.Length) return false;
}
return false;
}
public static void Main(string[] args) {
Solution sol = new Solution();
string[] words = {"i", "love", "leetcode", "apples"};
Console.WriteLine(sol.IsPrefixString("iloveleetcode", words));
}
}In this Python implementation, a simple loop and string concatenation check if the accumulating string matches s or gets longer than it.
Time Complexity: O(n * m) where n is the number of words and m is the average length of words.
Space Complexity: O(mn) for storing the concatenated string.
Approach 2: Prefix Matching With Removal
This alternative approach involves checking prefixes of s using each word, iteratively removing the matching prefix from s. Continue until either s becomes empty (indicating a full match) or a non-matching word is encountered. This method directly compares sections of s with each word.
def is_prefix_string(s, words):
index = 0
for word in words:
if index + len(word) > len(s):
return False
if s[index:index+len(word)] == word:
index += len(word)
if index == len(s):
return True
else:
return False
return False
s = "iloveleetcode"
words = ["i", "love", "leetcode", "apples"]
print(is_prefix_string(s, words))public class Solution {
public boolean isPrefixString(String s, String[] words) {
int index = 0;
for (String word : words) {
if (index + word.length() > s.length()) return false;
if (s.startsWith(word, index)) {
index += word.length();
if (index == s.length()) return true;
} else {
return false;
}
}
return false;
}
public static void main(String[] args) {
Solution sol = new Solution();
String[] words = {"i", "love", "leetcode", "apples"};
System.out.println(sol.isPrefixString("iloveleetcode", words));
}
}#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool isPrefixString(string s, vector<string>& words) {
int index = 0;
for (const string& word : words) {
if (index + word.length() > s.length()) return false;
if (s.substr(index, word.length()) == word) {
index += word.length();
if (index == s.length()) return true;
} else {
return false;
}
}
return false;
}
int main() {
vector<string> words = {"i", "love", "leetcode", "apples"};
string s = "iloveleetcode";
cout << (isPrefixString(s, words) ? "true" : "false") << endl;
return 0;
}function isPrefixString(s, words) {
let index = 0;
for (let word of words) {
if (index + word.length > s.length) return false;
if (s.slice(index, index + word.length) === word) {
index += word.length;
if (index === s.length) return true;
} else {
return false;
}
}
return false;
}
const s = "iloveleetcode";
const words = ["i", "love", "leetcode", "apples"];
console.log(isPrefixString(s, words));#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool isPrefixString(char *s, char **words, int wordsSize) {
size_t s_len = strlen(s), index = 0;
for (int i = 0; i < wordsSize; i++) {
size_t word_len = strlen(words[i]);
if (index + word_len > s_len) return false;
if (strncmp(s + index, words[i], word_len) == 0) {
index += word_len;
if (index == s_len) return true;
} else {
return false;
}
}
return false;
}
int main() {
char *words[] = {"i", "love", "leetcode", "apples"};
char *s = "iloveleetcode";
printf("%s\n", isPrefixString(s, words, 4) ? "true" : "false");
return 0;
}using System;
public class Solution {
public bool IsPrefixString(string s, string[] words) {
int index = 0;
foreach (var word in words) {
if (index + word.Length > s.Length) return false;
if (s.Substring(index, word.Length) == word) {
index += word.Length;
if (index == s.Length) return true;
} else {
return false;
}
}
return false;
}
public static void Main(string[] args) {
Solution sol = new Solution();
string[] words = {"i", "love", "leetcode", "apples"};
Console.WriteLine(sol.IsPrefixString("iloveleetcode", words));
}
}In Python, a simplified slice-based check ensures each word matches the start of the current s position, with success when s is completely matched.
Time Complexity: O(n * m) where n is the number of words and m is the average length of each word.
Space Complexity: O(1) for the constant extra space utilized.
Approach 3: Traversal
We traverse the array words, using a variable t to record the currently concatenated string. If the length of t is greater than the length of s, it means that s is not a prefix string of words, so we return false; if the length of t is equal to the length of s, we return whether t is equal to s.
At the end of the traversal, if the length of t is less than the length of s, it means that s is not a prefix string of words, so we return false.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string s.
function isPrefixString(s: string, words: string[]): boolean {
const t: string[] = [];
const n = s.length;
let m = 0;
for (const w of words) {
m += w.length;
if (m > n) {
return false;
}
t.push(w);
if (m === n) {
return s === t.join('');
}
}
return false;
}func isPrefixString(s string, words []string) bool {
t := strings.Builder{}
for _, w := range words {
t.WriteString(w)
if t.Len() > len(s) {
return false
}
if t.Len() == len(s) {
return t.String() == s
}
}
return false
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Concatenation | Time Complexity: |
| Prefix Matching With Removal | Time Complexity: |
| Traversal | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Concatenation | O(n) | O(n) | Simple implementation when memory overhead from building strings is acceptable |
| Prefix Matching With Removal | O(n) | O(1) | Preferred solution when you want optimal space and direct character comparison |
Frequently asked questions
Is Check If String Is a Prefix of Array easy or hard?
LeetCode classifies this problem as Easy. It mainly tests understanding of string traversal, array iteration, and careful pointer movement rather than advanced algorithms.
Check If String Is a Prefix of Array Python/Java solution
In Python or Java, iterate through the words array and compare characters of each word against the current index in s. Stop once s is fully matched or a mismatch occurs. The logic is identical across languages and runs in O(n) time.
How to solve Check If String Is a Prefix of Array in O(n)?
Use a pointer index for string s and iterate through the words array from the beginning. Compare each character of the current word with s[index]. Increment the index as matches occur. If the index reaches the length of s exactly, return true; if a mismatch occurs or words end early, return false.
What is the best approach for Check If String Is a Prefix of Array?
Prefix matching with a pointer over the target string is the best approach. Instead of concatenating all words, iterate through each word and compare characters directly with the string s. This processes each character once, giving O(n) time complexity and O(1) extra space.
Is Check If String Is a Prefix of Array asked at Google/Amazon/Meta?
This problem represents a common string and array traversal pattern often used in interviews at large tech companies. While the exact question may vary, similar prefix-checking or sequential matching problems appear in screening rounds at companies like Amazon and Google.
What data structure is used in Check If String Is a Prefix of Array?
The solution primarily uses arrays and strings with sequential traversal. No advanced data structures are required. The optimal method relies on pointer-style iteration, a common pattern in two pointers and string processing problems.
What is the time complexity of Check If String Is a Prefix of Array?
The optimal solution runs in O(n) time, where n is the total number of characters examined across s and the prefix portion of words. Each character is compared at most once. Space complexity can be O(1) if you avoid building intermediate strings.