1961. Check If String Is a Prefix of Array
Problem Description
The problem gives us two primary inputs: a string s
and an array of strings words
. The core task is to determine whether the string s
can be constructed by concatenating the first k
strings from the words
array, where k
is a positive integer and cannot exceed the length of words
. If s
can be created in this way, we refer to it as a prefix string of words
.
Intuition
To approach this problem, our main goal is to check if s
matches with a concatenation of the beginning subset of words
. To do that, we can iterate through the words
array and keep concatenating words until the total length of concatenated words equals the length of s
. The solution approach is straightforward:
- We maintain a running total of the lengths of the strings we have taken from the
words
array. - For each word in
words
, we increase this running total by the length of the current word. - If at any point the running total matches the length of
s
, we then check if the concatenation of the words thus far equalss
. - If the concatenation is a match, we return
true
indicatings
is a prefix string. - If we traverse all of
words
without finding a match, we returnfalse
.
The loop breaks early if the total length of concatenated words exceeds the length of s
since it cannot possibly be a prefix string if it's longer than s
.
Solution Approach
The solution implementation uses a simple algorithmic approach utilizing elementary control structures found in Python:
- We initialize a variable
t
to 0. This variable serves as the running total of lengths of strings from thewords
array that have been concatenated. - We iterate over each word
w
in thewords
array using afor
loop, and with each iteration, we add the length ofw
to our running totalt
. - For each word, after updating
t
, we comparet
with the length ofs
to check if we've reached or exceeded the length ofs
.- If the length
t
is equal to the length ofs
, we concatenate allwords
up to the currenti
index (through slicingwords[: i + 1]
) and compare the concatenated result withs
. - If they match,
s
is indeed a prefix string, and we returntrue
. - If the lengths match but the strings do not, or if we finish the loop without ever matching lengths, we return
false
.
- If the length
- The code exploits Python's list slicing and string joining capabilities to achieve this without needing a separate string builder or array.
Here is a step-by-step breakdown of the algorithm:
- Set
t = 0
. - Loop
i, w in enumerate(words)
:t += len(w)
increases total concatenated length.- Check if
len(s) == t
to see if lengths match.- If they do, verify string match with
''.join(words[: i + 1]) == s
. - If match is true, return
true
.
- If they do, verify string match with
- If no match is found after the loop completes, return
false
.
This algorithm uses a linear approach, iterating over the array once and stopping early if a match is found. On a complexity level, it operates in O(n) time with respect to the number of words, and potentially O(m) with respect to the length of s
because of the string comparison step.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach.
Suppose we have a string s = "applepenapple"
and an array of strings words = ["apple", "pen"]
. We want to determine if s
can be formed by concatenating the entire words
array.
Here are the steps we would follow:
- We initialize
t
to 0. This is our running total of the lengths of the strings we've concatenated from thewords
array. - We begin a loop over
words
withi, w in enumerate(words)
:- For the first iteration,
w = "apple"
andt
is updated tot += len(w)
which givest = 5
. - We then compare
t
withlen(s)
. Sincelen(s) = 13
andt = 5
, they do not match, so we continue without checking for a string match.
- For the first iteration,
- In the second iteration:
w = "pen"
and nowt
is updated tot += len(w)
which results int = 8
.- We compare
t
withlen(s)
again. Sincelen(s) = 13
andt = 8
, they still do not match, so we continue.
- Since we've reached the end of the
words
array withoutt
equalinglen(s)
, we continue to concatenate the words from the beginning of thewords
array untilt
equalslen(s)
, if possible. - The concatenated result of
words
is"applepen"
, which does not match the entire strings = "applepenapple"
. - Even if we repeat the
words
array once more (which is not part of this solution but just for understanding), the concatenated result would be"applepenapplepen"
, which exceedss
. - Since we cannot form
s
by concatenating thewords
array, the final result would befalse
.
In this example, s
cannot be a prefix string of words
because the concatenation of all the strings in words
does not equal s
, and furthermore, there is remaining substring in s
that can’t be matched by elements within words
. Thus, following the solution approach, we return false
.
Solution Implementation
1from typing import List # This line is to import the List type from the typing module
2
3class Solution:
4 def isPrefixString(self, s: str, words: List[str]) -> bool:
5 # Initialize total_length to 0 to keep track of the combined length of words in "words"
6 total_length = 0
7
8 # Iterate over the words list with an index i and word w
9 for i, word in enumerate(words):
10 # Update total_length by adding the length of the current word
11 total_length += len(word)
12
13 # Check if the combined length of words matches the length of s
14 if len(s) == total_length:
15 # Check if the concatenated words from the begin up to the current word equals s
16 # If it matches, our string s is a prefix and we return True
17 return ''.join(words[: i + 1]) == s
18
19 # If no prefix match is found after iterating through all words, return False
20 return False
21
1class Solution {
2 public boolean isPrefixString(String s, String[] words) {
3 // Initialize a StringBuilder to construct the prefix from words array
4 StringBuilder prefix = new StringBuilder();
5
6 // Iterate through each word in the words array
7 for (String word : words) {
8 // Append the current word to the prefix
9 prefix.append(word);
10
11 // Check if the length of the constructed prefix is same as the input string
12 if (s.length() == prefix.length()) {
13 // Compare the constructed prefix with the input string
14 return s.equals(prefix.toString());
15 }
16 }
17
18 // Return false if no prefix matches the input string
19 return false;
20 }
21}
22
1class Solution {
2public:
3 // Function to determine if the given string 's' is a prefix string
4 // created by concatenating elements from 'words' array.
5 bool isPrefixString(string s, vector<string>& words) {
6 string currentConcatenation = ""; // This will store the concatenation of words so far.
7
8 // Iterate over the words in the given words vector.
9 for (const string& word : words) {
10 // Add the current word to our concatenation string.
11 currentConcatenation += word;
12
13 // Check if the length of the current concatenation matches the length of 's'.
14 // If they match, perform a value comparison to see if they are equal.
15 if (currentConcatenation.size() == s.size()) {
16 return currentConcatenation == s; // Return true if they're exactly the same.
17 }
18 }
19 // If we exit the loop, the prefix condition has not been met.
20 return false;
21 }
22};
23
1// Function to determine if the given string 's' is a prefix string
2// created by concatenating elements from 'words' array.
3function isPrefixString(s: string, words: string[]): boolean {
4 let currentConcatenation: string = ""; // This will store the concatenation of words so far.
5
6 // Iterate over the words in the given words array.
7 for (const word of words) {
8 // Add the current word to our concatenation string.
9 currentConcatenation += word;
10
11 // Check if the length of the current concatenation matches the length of 's'.
12 // If they match, perform a value comparison to see if they are equal.
13 if (currentConcatenation.length === s.length) {
14 return currentConcatenation === s; // Return true if they're exactly the same.
15 }
16 }
17
18 // If we exit the loop, any prefix created doesn't match 's' exactly.
19 return false;
20}
21
Time and Space Complexity
Time Complexity
The time complexity of the code is O(n*k)
where n
is the number of words in the list and k
is the average length of the words. This is because in the worst case, the code iterates through each word in the words
list (O(n)
) and for each word it adds the length of the word to t
(O(k)
since in the worst case the length of the word can be as much as the length of s
). Moreover, joining the words is another O(n*k)
because all words might be joined in the worst case (when s
is exactly the concatenation of all words in the list).
Space Complexity
The space complexity is O(s)
, where s
is the length of the input string s
. In the worst case, when s
is a prefix string formed by concatenating all of the words in words
, the space taken by ''.join(words[:i + 1])
will be O(s)
since it needs to store the entire concatenated string equivalent to s
in memory temporarily.
Learn more about how to find time and space complexity quickly using problem constraints.
What does the following code do?
1def f(arr1, arr2):
2 i, j = 0, 0
3 new_arr = []
4 while i < len(arr1) and j < len(arr2):
5 if arr1[i] < arr2[j]:
6 new_arr.append(arr1[i])
7 i += 1
8 else:
9 new_arr.append(arr2[j])
10 j += 1
11 new_arr.extend(arr1[i:])
12 new_arr.extend(arr2[j:])
13 return new_arr
14
1public static List<Integer> f(int[] arr1, int[] arr2) {
2 int i = 0, j = 0;
3 List<Integer> newArr = new ArrayList<>();
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.add(arr1[i]);
8 i++;
9 } else {
10 newArr.add(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.add(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.add(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
1function f(arr1, arr2) {
2 let i = 0, j = 0;
3 let newArr = [];
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.push(arr1[i]);
8 i++;
9 } else {
10 newArr.push(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.push(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.push(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!