Leetcode – Check If String Is a Prefix of Array Solution

Spread the love

The question of checking if a given string is a prefix of an array is an interesting problem that combines elements of string manipulation and array traversal. This problem, titled “Check If String Is a Prefix of Array,” is listed on Leetcode and serves as a fantastic exercise for those looking to understand the basics of string and array operations in Python. Although it appears to be a straightforward problem at first glance, the variety of approaches and possible optimizations make it an interesting case study.

Problem Statement

Given a string s and an array of strings words, check if s is a prefix string of words. A string s is a prefix string of words if s can be made by concatenating some (possibly none) strings from words each at most once.

Return true if s is a prefix string of words, or false otherwise.

The objective is to determine if the given string s can be formed by concatenating full strings from the array words.

The Naive Approach: Iterative String Building

One approach to solve this problem is by iterating through the words array and building a new string by appending the words one by one, checking at each step if the new string matches the prefix of the target string s.

Python Code

def isPrefixString(s, words):
    built_string = ""
    for word in words:
        built_string += word
        if built_string == s:
            return True
        if len(built_string) > len(s) or built_string != s[:len(built_string)]:
            return False
    return False

Time Complexity

The time complexity for this approach is O(n), where n is the total length of the strings in the words array that are used to build the prefix string.

Optimized Approach: On-the-Fly Checking

Instead of building the string and comparing it to s at each step, we could perform the check on the fly as we iterate through the array. This allows us to break out of the loop as soon as we know that the string cannot be a prefix, which could potentially save some time.

Python Code

def isPrefixString(s, words):
    idx = 0  # Index for string 's'
    for word in words:
        for ch in word:
            if idx >= len(s) or ch != s[idx]:
                return False
            idx += 1
        if idx == len(s):
            return True
    return False

Time Complexity

The time complexity remains O(n) in the worst-case scenario. However, this approach has the potential to be faster in practical cases where the string s cannot be formed by the words array, as we can terminate the loop early.

Elegant Pythonic Way: Using str.startwith( ) Method

Python offers a built-in string method startswith(), which can be leveraged to make the code more readable and Pythonic.

Python Code

def isPrefixString(s, words):
    built_string = ""
    for word in words:
        built_string += word
        if built_string.startswith(s):
            return built_string == s
        if len(built_string) > len(s):
            return False
    return False

Time Complexity

The time complexity is O(n), similar to the previous approaches. However, the built-in method could offer some internal optimizations.

Conclusion

The “Check If String Is a Prefix of Array” problem offers a fundamental exercise in string and array manipulation. While the naive approach provides a straightforward way to solve the problem, optimized and Pythonic approaches offer nuanced ways to approach the problem with more efficiency and readability.

Leave a Reply