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 equals s.
  • If the concatenation is a match, we return true indicating s is a prefix string.
  • If we traverse all of words without finding a match, we return false.

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 the words array that have been concatenated.
  • We iterate over each word w in the words array using a for loop, and with each iteration, we add the length of w to our running total t.
  • For each word, after updating t, we compare t with the length of s to check if we've reached or exceeded the length of s.
    • If the length t is equal to the length of s, we concatenate all words up to the current i index (through slicing words[: i + 1]) and compare the concatenated result with s.
    • If they match, s is indeed a prefix string, and we return true.
    • If the lengths match but the strings do not, or if we finish the loop without ever matching lengths, we return false.
  • 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):
    1. t += len(w) increases total concatenated length.
    2. 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 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 Evaluator

Example 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 the words array.
  • We begin a loop over words with i, w in enumerate(words):
    1. For the first iteration, w = "apple" and t is updated to t += len(w) which gives t = 5.
    2. We then compare t with len(s). Since len(s) = 13 and t = 5, they do not match, so we continue without checking for a string match.
  • In the second iteration:
    1. w = "pen" and now t is updated to t += len(w) which results in t = 8.
    2. We compare t with len(s) again. Since len(s) = 13 and t = 8, they still do not match, so we continue.
  • Since we've reached the end of the words array without t equaling len(s), we continue to concatenate the words from the beginning of the words array until t equals len(s), if possible.
  • The concatenated result of words is "applepen", which does not match the entire string s = "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 exceeds s.
  • Since we cannot form s by concatenating the words array, the final result would be false.

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

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

Want a Structured Path to Master System Design Too? Don’t Miss This!