Problem

You are given a string array words and a string s, where words[i] and s comprise only of lowercase English letters.

Return thenumber of strings in words that are aprefix of s.

A prefix of a string is a substring that occurs at the beginning of the string. A substring is a contiguous sequence of characters within a string.

Examples

Example 1

1
2
3
4
5
6

Input: words = ["a","b","c","ab","bc","abc"], s = "abc"
Output: 3
Explanation:
The strings in words which are a prefix of s = "abc" are:
"a", "ab", and "abc".
Thus the number of strings in words which are a prefix of s is 3.

Example 2

1
2
3
4

Input: words = ["a","a"], s = "aa"
Output: 2
Explanation: Both of the strings are a prefix of s. 
Note that the same string can occur multiple times in words, and it should be counted each time.

Constraints

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

Solution

Method 1 – Simple Prefix Check

Intuition

A string is a prefix of another if it matches the beginning of that string. For each word, we can check if it is a prefix of s using a simple comparison.

Approach

  1. Initialize a counter ans to 0.
  2. For each word in words:
    1. If s starts with word, increment ans.
  3. Return ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    int countPrefixes(vector<string>& words, string s) {
        int ans = 0;
        for (auto& w : words) {
            if (s.substr(0, w.size()) == w) ans++;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9

func countPrefixes(words []string, s string) int {
    ans := 0
    for _, w := range words {
        if len(w) <= len(s) && s[:len(w)] == w {
            ans++
        }
    }
    return ans
}
1
2
3
4
5
6
7
8
9

class Solution {
    public int countPrefixes(String[] words, String s) {
        int ans = 0;
        for (String w : words) {
            if (s.startsWith(w)) ans++;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun countPrefixes(words: Array<String>, s: String): Int {
        var ans = 0
        for (w in words) {
            if (s.startsWith(w)) ans++
        }
        return ans
    }
}
1
2
3
4
5
6
7

class Solution:
    def countPrefixes(self, words: list[str], s: str) -> int:
        ans = 0
        for w in words:
            if s.startswith(w):
                ans += 1
        return ans
1
2
3
4
5

impl Solution {
    pub fn count_prefixes(words: Vec<String>, s: String) -> i32 {
        words.iter().filter(|w| s.starts_with(w.as_str())).count() as i32
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    countPrefixes(words: string[], s: string): number {
        let ans = 0;
        for (const w of words) {
            if (s.startsWith(w)) ans++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * m), where n is the number of words and m is the average word length (since each prefix check is O(m)).
  • 🧺 Space complexity: O(1), as we use only a counter.