Leetcode 1961: Check If String Is a Prefix of Array

Input: The input consists of a string `s` and an array of strings `words`. The string `s` is a potential prefix formed by concatenating the first `k` words from the array `words`.

Example: s = "hello", words = ["he", "llo"]

Constraints:

• 1 <= words.length <= 100

• 1 <= words[i].length <= 20

• 1 <= s.length <= 1000

• words[i] and s consist of only lowercase English letters.

Output: The output should be a boolean value indicating whether `s` is a prefix formed by concatenating the first `k` words in `words`.

Example: Output: true

Constraints:

• The string `s` must match the prefix formed by the concatenation of the words in `words`.

Goal: The goal is to check if the string `s` can be constructed by concatenating the first `k` strings in the array `words`.

Steps:

• Step 1: Traverse through the strings in `words`, concatenating them one by one.

• Step 2: Compare the concatenated string with `s` at each step.

• Step 3: If the concatenated string matches `s`, return true; otherwise, return false.

Goal: The problem constraints ensure that the length of `words` and `s` are manageable for efficient checking.

Steps:

• The length of `words` is at most 100.

• The length of each word is at most 20 characters.

• The length of `s` is at most 1000 characters.

Assumptions:

• The array `words` will not contain any empty strings.

• Input: Input: s = "hello", words = ["he", "llo"]

• Explanation: Here, the string `s` can be formed by concatenating the first two words from `words`, i.e., "he" + "llo" = "hello".

Approach: The approach is to concatenate the first `k` words from the array `words` and check if the concatenated string matches `s`.

Observations:

• The problem can be solved by simply iterating over the array `words` and checking for a match with `s`.

• Efficient string concatenation and comparison are key to solving this problem.

Steps:

• Step 1: Initialize a string variable to store the concatenation of words.

• Step 2: Iterate through the array `words`, concatenating each word to the string.

• Step 3: After each concatenation, compare the result with `s`. If they match, return true. If they don’t, continue the process.

• Step 4: If no match is found after processing all words, return false.

Empty Inputs:

• The string `s` and the array `words` will never be empty.

Large Inputs:

• Ensure that the solution handles large strings and arrays efficiently.

Special Values:

• Handle cases where `s` matches only a subset of the words in `words`.

Constraints:

• Make sure to respect the length constraints on both `s` and the elements of `words`.

bool isPrefixString(string s, vector<string>& w) {
    int k = 0, l = 0, i = 0;
    for(i = 0; i < s.size() && k < w.size(); i++) {
        
        if(s[i] != w[k][l]) return false;
        
        l++;
        
        if(l == w[k].size()) {
            k++;
            l = 0;
        }
    }
    if(i != s.size()) return false;
    return (l == 0);
}

1 : Variable Declaration

bool isPrefixString(string s, vector<string>& w) {

Declares the function `isPrefixString` that takes a string `s` and a vector of strings `w`. It will determine if `s` is a prefix of the concatenated strings in `w`.

2 : Variable Initialization

    int k = 0, l = 0, i = 0;

Initializes variables `k`, `l`, and `i` to track the current word index (`k`), character index in the current word (`l`), and the loop index (`i`).

3 : Looping

    for(i = 0; i < s.size() && k < w.size(); i++) {

Starts a loop to iterate over the characters in the string `s` while also making sure that the index `k` is within the bounds of the vector `w`.

4 : Comparison

        if(s[i] != w[k][l]) return false;

Compares the character `s[i]` with the current character `w[k][l]`. If they do not match, the function immediately returns `false`.

5 : Progressing Indexes

        l++;

Increments the index `l` to move to the next character in the current word `w[k]`.

6 : Word Completion Check

        if(l == w[k].size()) {

Checks if the entire current word `w[k]` has been matched. If true, it resets `l` to start comparing the next word.

7 : Word Transition

            k++;

Increments `k` to move to the next word in the vector `w` after successfully matching the current word.

8 : Reset Character Index

            l = 0;

Resets the index `l` to 0 to begin comparing from the start of the next word.

9 : Final Check

    if(i != s.size()) return false;

Checks if all characters of `s` have been matched. If not, it returns `false`.

10 : Return Result

    return (l == 0);

Returns `true` if `l` is 0, meaning the last word was fully matched and the string `s` is a valid prefix. Otherwise, returns `false`.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: In the worst case, we iterate through all `n` words and concatenate them, where `n` is the length of the `words` array.

Best Case: O(1)

Worst Case: O(n)

Description: The space complexity is O(n) due to the concatenation of strings from the array `words`.

Leetcode 1961: Check If String Is a Prefix of Array

Explore →