Check If String Is A Prefix Of Array - Leetcode Solution

Problem statement:

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:

Input: s = "iloveleetcode", words = ["i","love","leetcode","apples"] Output: true Explanation: s can be made by concatenating the first three strings in words.

Solution:

To solve this problem, we need to check whether the given string s can be formed by concatenating the first k strings in the given array words. For this, we can iterate through the array words and keep concatenating the strings until we get the desired string s. We also need to keep track of the number of strings we have used so far to form the string s.

We can use a variable called count to keep track of the number of strings used so far. Initially, count is set to zero. We can then iterate through the array words and concatenate each string to the string formed so far. If the concatenated string matches the string s, we return true. If count becomes greater than or equal to the length of words or the concatenated string becomes longer than s, we return false.

Here is the Python code for the solution:

def isPrefixString(s: str, words: List[str]) -> bool: count = 0 formed = "" for word in words: formed += word count += 1 if formed == s: return True if count >= len(words) or len(formed) >= len(s): return False return False

Time Complexity:

In the worst case, we need to iterate through all the strings in the array words to form the string s. Therefore, the time complexity of the above solution is O(n), where n is the length of the array words.

Space Complexity:

We are using a variable count and a string formed to keep track of the progress. Therefore, the space complexity of the above solution is O(n), where n is the length of the array words.

1