Solution Explanation for Check If String Is a Prefix of Array

This problem asks whether a given string s can be formed by concatenating the initial elements of a string array words. The solution involves iteratively concatenating strings from words and comparing the result with s.

Approach

The core idea is to maintain a running concatenation of strings from the words array. We stop when either:

1. The concatenated string's length exceeds s's length: This implies s cannot be a prefix.
2. The concatenated string's length equals s's length: We then perform a direct string comparison. If they are equal, s is a prefix; otherwise, it's not.
3. We exhaust all strings in words without reaching either of the above conditions: s is not a prefix.

Code Implementation (Python)

class Solution:
    def isPrefixString(self, s: str, words: List[str]) -> bool:
        prefix = ""
        for word in words:
            prefix += word
            if len(prefix) > len(s):
                return False  # Prefix is longer than s
            if len(prefix) == len(s):
                return prefix == s  # Check for equality
        return False  # Prefix shorter than s
 

Code Implementation (Other Languages) - Java, C++, Go, Javascript

The logic remains consistent across different programming languages. The primary differences lie in string manipulation syntax and data structures. Below are examples in Java, C++, Go, and Javascript. Note that error handling and edge cases (empty input, etc.) are generally omitted for brevity in these examples.

Java:

class Solution {
    public boolean isPrefixString(String s, String[] words) {
        StringBuilder prefix = new StringBuilder();
        for (String word : words) {
            prefix.append(word);
            if (prefix.length() > s.length()) return false;
            if (prefix.length() == s.length()) return prefix.toString().equals(s);
        }
        return false;
    }
}

C++:

class Solution {
public:
    bool isPrefixString(string s, vector<string>& words) {
        string prefix = "";
        for (const string& word : words) {
            prefix += word;
            if (prefix.length() > s.length()) return false;
            if (prefix.length() == s.length()) return prefix == s;
        }
        return false;
    }
};

Go:

func isPrefixString(s string, words []string) bool {
	prefix := ""
	for _, word := range words {
		prefix += word
		if len(prefix) > len(s) {
			return false
		}
		if len(prefix) == len(s) {
			return prefix == s
		}
	}
	return false
}

Javascript:

/**
 * @param {string} s
 * @param {string[]} words
 * @return {boolean}
 */
var isPrefixString = function(s, words) {
    let prefix = "";
    for (let word of words) {
        prefix += word;
        if (prefix.length > s.length) return false;
        if (prefix.length === s.length) return prefix === s;
    }
    return false;
};

Time and Space Complexity Analysis

• Time Complexity: O(N), where N is the total number of characters in the words array (and potentially the length of s). This is because we iterate through the words array once, and string concatenation and comparison take linear time relative to string lengths.

• Space Complexity: O(N) in the worst case. This is because the prefix string could potentially grow to the size of the concatenated words in the array. In many scenarios, it might be less, especially if a match is found early.

The space complexity can be optimized slightly by not storing prefix explicitly and instead using the string's length to make the comparison. However, this optimization doesn't change the overall asymptotic complexity.