Open yankewei opened 2 years ago
这个题第一直觉可以用模拟来做,如果一个字符串 a 是 另一个字符串 b 的子字符串,那么 a 的长度肯定小于 b,并且题目要求返回值不需要有顺序,所以可以先根据字符串的长度对数组进行排序,方便我们去遍历.
class Solution {
/**
* @param String[] $words
* @return String[]
*/
function stringMatching($words) {
$result = [];
usort($words, fn($a, $b) => strlen($a) > strlen($b) ? 1 : -1);
for ($i = 0; $i < count($words); $i++) {
for ($j = $i+1; $j < count($words); $j++) {
if (strstr($words[$j], $words[$i]) !== false) {
$result[] = $words[$i];
break;
}
}
}
return $result;
}
}
另一种解法把数组元素拼接成一个长字符串 str ,然后再去查找,如果一个元素在 str 中出现至少两次(一次是自己,一次是在另一个字符串的子字符串),比如["et","code","leetcode"]
,拼接之后的字符串是etcodeleetcode
,et
出现了两次,一个是自己,另一次是做为leetcode
的子字符串。但是这个解法有两个需要注意的点:
["abc","de","abcd"]
,abcd
出现了两次,但其实它不是我们需要的。class Solution {
/**
* @param String[] $words
* @return String[]
*/
function stringMatching($words) {
$result = [];
$str = implode('+', $words);
foreach ($words as $word) {
if (strpos(substr($str, strpos($str, $word) + strlen($word)), $word) !== false) {
$result[] = $word;
}
}
return $result;
}
}
func stringMatching(words []string) []string {
str := strings.Join(words, "+")
result := []string{}
for _, word := range words {
if (strings.Index(string(str[strings.Index(str, word) + len(word):]), word) != -1) {
result = append(result, word)
}
}
return result
}
给你一个字符串数组 words ,数组中的每个字符串都可以看作是一个单词。请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。
如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ,那么字符串 words[i] 就是 words[j] 的一个子字符串。
示例 1:
示例 2:
示例 3:
提示:
来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/string-matching-in-an-array 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。