Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1408.html
1408. String Matching in an Array (Easy)
Given an array of string words
. Return all strings in words
which is substring of another word in any order.
String words[i]
is substring of words[j]
, if can be obtained removing some characters to left and/or right side of words[j]
.
Example 1:
Input: words = ["mass","as","hero","superhero"] Output: ["as","hero"] Explanation: "as" is substring of "mass" and "hero" is substring of "superhero". ["hero","as"] is also a valid answer.
Example 2:
Input: words = ["leetcode","et","code"] Output: ["et","code"] Explanation: "et", "code" are substring of "leetcode".
Example 3:
Input: words = ["blue","green","bu"] Output: []
Constraints:
1 <= words.length <= 100
1 <= words[i].length <= 30
words[i]
contains only lowercase English letters.- It's guaranteed that
words[i]
will be unique.
Related Topics:
String
Solution 1. Brute force
For each words[i]
, check if it’s a substring of words[j]
(0 <= j < N && i != j
). Once find a match, we can push words[i]
to result and continue to word[i + 1]
.
// OJ: https://leetcode.com/problems/string-matching-in-an-array/
// Time: O(N^2 * D)
// Space: O(1)
class Solution {
public:
vector<string> stringMatching(vector<string>& words) {
vector<string> ans;
int N = words.size();
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (i == j) continue;
if (words[j].find(words[i]) != string::npos) {
ans.push_back(words[i]);
break;
}
}
}
return ans;
}
};
-
class Solution { public List<String> stringMatching(String[] words) { Arrays.sort(words, new Comparator<String>() { public int compare(String word1, String word2) { return word1.length() - word2.length(); } }); List<String> list = new ArrayList<String>(); int length = words.length; for (int i = 0; i < length; i++) { String word1 = words[i]; boolean flag = false; for (int j = i + 1; j < length; j++) { String word2 = words[j]; if (word2.indexOf(word1) >= 0) { flag = true; break; } } if (flag) list.add(word1); } return list; } } ############ class Solution { public List<String> stringMatching(String[] words) { List<String> ans = new ArrayList<>(); int n = words.length; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i != j && words[j].contains(words[i])) { ans.add(words[i]); break; } } } return ans; } }
-
// OJ: https://leetcode.com/problems/string-matching-in-an-array/ // Time: O(N^2 * D) // Space: O(1) class Solution { public: vector<string> stringMatching(vector<string>& words) { vector<string> ans; int N = words.size(); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (i == j) continue; if (words[j].find(words[i]) != string::npos) { ans.push_back(words[i]); break; } } } return ans; } };
-
class Solution: def stringMatching(self, words: List[str]) -> List[str]: ans = [] for i, w1 in enumerate(words): for j, w2 in enumerate(words): if i != j and w1 in w2: ans.append(w1) break return ans ############ class Solution: def stringMatching(self, words: List[str]) -> List[str]: res = set() for word in words: for cur in words: if cur in word and cur != word: res.add(cur) return list(res)
-
func stringMatching(words []string) []string { ans := []string{} for i, w1 := range words { for j, w2 := range words { if i != j && strings.Contains(w2, w1) { ans = append(ans, w1) break } } } return ans }
-
function stringMatching(words: string[]): string[] { const res: string[] = []; for (const target of words) { for (const word of words) { if (word !== target && word.includes(target)) { res.push(target); break; } } } return res; }
-
impl Solution { pub fn string_matching(words: Vec<String>) -> Vec<String> { let mut res = Vec::new(); for target in words.iter() { for word in words.iter() { if word != target && word.contains(target) { res.push(target.clone()); break; } } } res } }