字符串的匹配算法，暴力和手写实现 KMP，自定义排序的升序排列、合并字符串技巧，求解《1408. 数组中的字符串匹配》
1408. 数组中的字符串匹配
给你一个字符串数组 words ，数组中的每个字符串都可以看作是一个单词。请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。
如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ，那么字符串 words[i] 就是 words[j] 的一个子字符串。
示例 1：
输入：words = ["mass","as","hero","superhero"]
输出：["as","hero"]
解释："as" 是 "mass" 的子字符串，"hero" 是 "superhero" 的子字符串。
["hero","as"] 也是有效的答案。
答案
暴力 · 自定义排序 · 升序
将字符串按长度升序排列，减少比较次数
var stringMatching = function(words) {
words.sort((a, b) => a.length - b.length)
const n = words.length, r = []
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (words[j].includes(words[i])) {
r.push(words[i])
break
}
}
}
return r
};class Solution {
function stringMatching($words) {
usort($words, function($a, $b) {
return strlen($a) > strlen($b);
});
$n = count($words);
$r = array();
for ($i = 0; $i < $n; $i++) {
for ($j = $i + 1; $j < $n; $j++) {
if (stripos($words[$j], $words[$i]) > -1) {
$r []= $words[$i];
break;
}
}
}
return $r;
}
}func stringMatching(words []string) []string {
sort.SliceStable(words, func(i, j int) bool {
return len(words[i]) < len(words[j])
})
n, r := len(words), []string{}
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if strings.Contains(words[j], words[i]) {
r = append(r, words[i])
break
}
}
}
return r
}class Solution {
public List<String> stringMatching(String[] words) {
Arrays.sort(words, (a, b) -> a.length() - b.length());
int n = words.length;
List<String> r = new ArrayList<String>();
label: for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (words[j].contains(words[i])) {
r.add(words[i]);
continue label;
}
}
}
return r;
}
}public class Solution {
public IList<string> StringMatching(string[] words) {
Array.Sort(words, delegate(string a, string b) {
return a.Length - b.Length;
});
int n = words.Length;
IList<string> r = new List<string>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (words[j].Contains(words[i])) {
r.Add(words[i]);
break;
}
}
}
return r;
}
}static inline int cmp (const void *pa, const void *pb) {
return strlen(*(char **)pa) - strlen(*(char **)pb);
}
char ** stringMatching(char ** words, int wordsSize, int* returnSize){
qsort(words, wordsSize, sizeof(char *), cmp);
char ** r = malloc(sizeof(char *) * wordsSize);
int pos = 0;
for (int i = 0; i < wordsSize; i++) {
for (int j = i + 1; j < wordsSize; j++) {
if (strstr(words[j], words[i])) {
r[pos++] = words[i];
break;
}
}
}
r[pos] = '\0';
*returnSize = pos;
return r;
}class Solution {
private:
static inline bool cmp (const string a, const string b) {
return a.size() < b.size();
}
public:
vector<string> stringMatching(vector<string>& words) {
sort(words.begin(), words.end(), cmp);
int n = words.size();
vector<string> r;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (words[j].find(words[i]) != string::npos) {
r.push_back(words[i]);
break;
}
}
}
return r;
}
};class Solution:
def stringMatching(self, words: List[str]) -> List[str]:
words.sort(key = lambda k: len(k))
n = len(words)
r = []
for i in range(0, n):
for j in range(i + 1, n):
if words[i] in words[j]:
r.append(words[i])
break
return r暴力 · 合并字符串
将字符串用非字母合并，统计出现次数 >= 2 的字符串
var stringMatching = function(words) {
const s = words.join('-'), r = []
for (const w of words) if (s.split(w).length > 2) r.push(w)
return r
};class Solution {
function stringMatching($words) {
$s = implode('-', $words);
$r = [];
foreach($words as $w) {
if (substr_count($s, $w) > 1) $r []= $w;
}
return $r;
}
}func stringMatching(words []string) []string {
s, r := strings.Join(words, "-"), []string{}
for _, w := range words {
if strings.Count(s, w) > 1 {
r = append(r, w)
}
}
return r
}class Solution {
public List<String> stringMatching(String[] words) {
String s = String.join("-", words) + "-"; // 加一个字符 避免分隔符刚好出现在字符串尾部
List<String> r = new ArrayList<String>();
for (String word : words) {
if (s.split(word).length > 2) r.add(word);
}
return r;
}
}public class Solution {
public IList<string> StringMatching(string[] words) {
string s = string.Join('-', words);
IList<string> r = new List<string>();
foreach (string w in words) {
if (s.Split(w).Length > 2) r.Add(w);
}
return r;
}
}class Solution:
def stringMatching(self, words: List[str]) -> List[str]:
return [w for w in words if "-".join(words).count(w) > 1]暴力 · KMP 算法
var stringMatching = function(words) {
const n = words.length, r = []
label: for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (i !== j && words[j].length > words[i].length && strstr(words[j], words[i])) {
r.push(words[i])
continue label
}
}
}
return r
};
const strstr = function (s, p) {
const m = p.length, next = new Uint8Array(m)
for (let i = 1, j = 0; i < m; i++) {
while (j > 0 && p[i] !== p[j]) j = next[j - 1]
if (p[i] === p[j]) j++
next[i] = j
}
const n = s.length
for (let i = 0, j = 0; i < n; i++) {
while (j > 0 && s[i] !== p[j]) j = next[j - 1]
if (s[i] === p[j]) j++
if (j === m) return true
}
return false
}function stringMatching(words: string[]): string[] {
const n = words.length, r = []
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (i !== j && words[j].length > words[i].length && strstr(words[j], words[i])) {
r.push(words[i])
break
}
}
}
return r
};
function strstr(s: string, p: string): boolean {
const m = p.length, next = new Array(m).fill(0)
for (let i = 1, j = 0; i < m; i++) {
while (j > 0 && p[i] !== p[j]) j = next[j - 1]
if (p[i] === p[j]) j++
next[i] = j
}
const n = s.length
for (let i = 0, j = 0; i < n; i++) {
while (j > 0 && s[i] !== p[j]) j = next[j - 1]
if (s[i] === p[j]) j++
if (j === m) return true
}
return false
}static inline bool strstrKMP (char* s, char* p) {
int m = strlen(p);
int* next = malloc(sizeof(int) * m);
memset(next, 0, sizeof(int) * m);
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && p[i] != p[j]) j = next[j - 1];
if (p[i] == p[j]) j++;
next[i] = j;
}
int n = strlen(s);
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && s[i] != p[j]) j = next[j - 1];
if (s[i] == p[j]) j++;
if (j == m) return true;
}
return false;
}
char ** stringMatching(char ** words, int wordsSize, int* returnSize){
char ** r = malloc(sizeof(char *) * wordsSize);
int pos = 0;
for (int i = 0; i < wordsSize; i++) {
for (int j = 0; j < wordsSize; j++) {
if (i != j && strlen(words[j]) > strlen(words[i]) && strstrKMP(words[j], words[i])) {
r[pos++] = words[i];
break;
}
}
}
r[pos] = '\n';
*returnSize = pos;
return r;
}class Solution {
private:
static bool strstr(string s, string p) {
int m = p.size();
vector<int> next(m, 0);
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && p[i] != p[j]) j = next[j - 1];
if (p[i] == p[j]) j++;
next[i] = j;
}
int n = s.size();
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && s[i] != p[j]) j = next[j - 1];
if (s[i] == p[j]) j++;
if (j == m) return true;
}
return false;
}
public:
vector<string> stringMatching(vector<string>& words) {
int n = words.size();
vector<string> r;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j && words[j].size() > words[i].size() && strstr(words[j], words[i])) {
r.push_back(words[i]);
break;
}
}
}
return r;
}
};class Solution:
def strstr(self, s: str, p: str) -> bool:
m, j = len(p), 0
nexts = [0] * m
for i in range(1, m):
while j > 0 and p[i] != p[j]: j = nexts[j - 1]
if p[i] == p[j]: j += 1
nexts[i] = j
n, j = len(s), 0
for i in range(0, n):
while j > 0 and s[i] != p[j]: j = nexts[j - 1]
if s[i] == p[j]: j += 1
if j == m: return True
return False
def stringMatching(self, words: List[str]) -> List[str]:
return list(set(a for a in words for b in words if a != b and self.strstr(b, a)))class Solution:
def stringMatching(self, words: List[str]) -> List[str]:
return list(set(a for j, a in enumerate(words) for i, b in enumerate(words) if i != j and len(b) > len(a) and a in b))