We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check If String Is a Prefix of Array

Number: 2093

Difficulty: Easy

Paid? No

Companies: Uber

Problem Description

Given a string s and an array of strings words, determine whether s is a prefix string of words. In other words, check if s can be obtained by concatenating the first k strings in words for some positive integer k (where k is no larger than the number of elements in words).

Key Insights

  • Iterate through the words and cumulatively build a string.
  • After adding each word, compare the accumulated string with s.
  • Return true immediately when the accumulated string matches s.
  • If the accumulated string exceeds the length of s without a match, it is impossible for s to be a prefix.
  • Early termination improves efficiency.

Space and Time Complexity

Time Complexity: O(n * m) in the worst case where n is the number of words and m is the average length of each word, because we might concatenate and compare strings at each iteration. Space Complexity: O(m) for storing the accumulated prefix string.

Solution

We solve this problem by accumulating words one by one into a temporary string and checking at each step if the accumulated string equals s. The process stops early if the accumulated string becomes longer than s. This avoids unnecessary calculations and ensures an efficient solution. The primary data structure used is a simple string (or StringBuilder in Java) to record the prefix, and the algorithm iterates through the array with simple string concatenation and comparison operations.

Code Solutions

# Define the function that checks if s is a prefix string of words
def check_if_prefix_string(s, words):
    # Initialize an empty string to accumulate the prefix
    prefix = ""
    # Iterate over each word in the words list
    for word in words:
        # Append the current word to the accumulated prefix
        prefix += word
        # Check if the accumulated prefix matches s
        if prefix == s:
            return True
        # If the accumulated prefix exceeds the length of s, no need to continue
        if len(prefix) > len(s):
            return False
    # If no matching prefix is found, return False
    return False

# Example usage
print(check_if_prefix_string("iloveleetcode", ["i", "love", "leetcode", "apples"]))
← Back to All Questions