Problem

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 ifs _is aprefix string of _words , orfalse otherwise.

Examples

Example 1

1
2
3
4

Input: s = "iloveleetcode", words = ["i","love","leetcode","apples"]
Output: true
Explanation:
s can be made by concatenating "i", "love", and "leetcode" together.

Example 2

1
2
3
4

Input: s = "iloveleetcode", words = ["apples","i","love","leetcode"]
Output: false
Explanation:
It is impossible to make s using a prefix of arr.

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 20
  • 1 <= s.length <= 1000
  • words[i] and s consist of only lowercase English letters.

Solution

Method 1 – Two Pointers (Prefix Check)

Intuition

We want to check if the string s can be formed by concatenating the first k words from the array. This is a straightforward prefix check using two pointers: one for the string and one for the array.

Reasoning

By iterating through the words and matching their characters with the corresponding characters in s, we can verify if s is a prefix. If we reach the end of s exactly after some words, then s is a prefix of the array.

Approach

  1. Initialize a pointer i for the string s at 0.
  2. Iterate through each word in words:
    • For each character in the word, check if it matches s[i].
    • If any character does not match or if i exceeds the length of s, return false.
    • Increment i for each matched character.
    • If i reaches the length of s, return true (all of s matched).
  3. If the loop ends and i is not equal to the length of s, return false.

Edge cases:

  • s is shorter than the concatenation of all words.
  • s is longer than the concatenation of all words.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    bool isPrefixString(string s, vector<string>& words) {
        int i = 0;
        for (const string& w : words) {
            for (char c : w) {
                if (i == s.size() || s[i] != c) return false;
                ++i;
            }
            if (i == s.size()) return true;
        }
        return i == s.size();
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func isPrefixString(s string, words []string) bool {
    i := 0
    for _, w := range words {
        for _, c := range w {
            if i == len(s) || s[i] != byte(c) {
                return false
            }
            i++
        }
        if i == len(s) {
            return true
        }
    }
    return i == len(s)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public boolean isPrefixString(String s, String[] words) {
        int i = 0;
        for (String w : words) {
            for (char c : w.toCharArray()) {
                if (i == s.length() || s.charAt(i) != c) return false;
                i++;
            }
            if (i == s.length()) return true;
        }
        return i == s.length();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun isPrefixString(s: String, words: Array<String>): Boolean {
        var i = 0
        for (w in words) {
            for (c in w) {
                if (i == s.length || s[i] != c) return false
                i++
            }
            if (i == s.length) return true
        }
        return i == s.length
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def is_prefix_string(self, s: str, words: list[str]) -> bool:
        i = 0
        for w in words:
            for c in w:
                if i == len(s) or s[i] != c:
                    return False
                i += 1
            if i == len(s):
                return True
        return i == len(s)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn is_prefix_string(s: String, words: Vec<String>) -> bool {
        let mut i = 0;
        let s_bytes = s.as_bytes();
        for w in words {
            for &c in w.as_bytes() {
                if i == s_bytes.len() || s_bytes[i] != c {
                    return false;
                }
                i += 1;
            }
            if i == s_bytes.len() {
                return true;
            }
        }
        i == s_bytes.len()
    }
}

Complexity

  • ⏰ Time complexity: O(n), as we scan each character of s at most once, where n is the length of s.
  • 🧺 Space complexity: O(1), as we use only a few variables for tracking indices.