Skip to content

1967. Number of Strings That Appear as Substrings in Word

Description

Given an array of strings patterns and a string word, return the number of strings in patterns that exist as a substring in word.

A substring is a contiguous sequence of characters within a string.

 

Example 1:

Input: patterns = ["a","abc","bc","d"], word = "abc"
Output: 3
Explanation:
- "a" appears as a substring in "abc".
- "abc" appears as a substring in "abc".
- "bc" appears as a substring in "abc".
- "d" does not appear as a substring in "abc".
3 of the strings in patterns appear as a substring in word.

Example 2:

Input: patterns = ["a","b","c"], word = "aaaaabbbbb"
Output: 2
Explanation:
- "a" appears as a substring in "aaaaabbbbb".
- "b" appears as a substring in "aaaaabbbbb".
- "c" does not appear as a substring in "aaaaabbbbb".
2 of the strings in patterns appear as a substring in word.

Example 3:

Input: patterns = ["a","a","a"], word = "ab"
Output: 3
Explanation: Each of the patterns appears as a substring in word "ab".

 

Constraints:

  • 1 <= patterns.length <= 100
  • 1 <= patterns[i].length <= 100
  • 1 <= word.length <= 100
  • patterns[i] and word consist of lowercase English letters.

Solutions

Solution 1: Simulation

Traverse each string \(p\) in the array \(\textit{patterns}\) and check if it is a substring of \(\textit{word}\). If it is, increment the answer by one.

After traversing, return the answer.

The time complexity is \(O(n \times m)\), and the space complexity is \(O(1)\). Here, \(n\) and \(m\) are the lengths of \(\textit{patterns}\) and \(\textit{word}\), respectively.

1
2
3
class Solution:
    def numOfStrings(self, patterns: List[str], word: str) -> int:
        return sum(p in word for p in patterns)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int numOfStrings(String[] patterns, String word) {
        int ans = 0;
        for (String p : patterns) {
            if (word.contains(p)) {
                ++ans;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    int numOfStrings(vector<string>& patterns, string word) {
        int ans = 0;
        for (auto& p : patterns) {
            ans += word.find(p) != string::npos;
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
func numOfStrings(patterns []string, word string) (ans int) {
    for _, p := range patterns {
        if strings.Contains(word, p) {
            ans++
        }
    }
    return
}

1
2
3
function numOfStrings(patterns: string[], word: string): number {
    return patterns.filter(p => word.includes(p)).length;
}

1
2
3
4
5
impl Solution {
    pub fn num_of_strings(patterns: Vec<String>, word: String) -> i32 {
        patterns.iter().filter(|p| word.contains(&**p)).count() as i32
    }
}

Comments