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;
}
};
Java
-
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; } }
-
// 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]: res = set() for word in words: for cur in words: if cur in word and cur != word: res.add(cur) return list(res)