暴力(自定义排序、合并字符串技巧),KMP 2 种算法, 求解《1408. 数组中的字符串匹配》

2022-08-06 17:50:47
字符串的匹配算法,暴力和手写实现 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))

顺序遍历字符串,双指针技巧,用 startsWith (javascript / typescript / java) / StartsWith (c#) / startswith (python) / str_starts_with (php) / strings.HasPrefix (golang)接口,求解《1455. 检查单词是否为句中其他单词的前缀》
顺序遍历字符串,双指针技巧,用 startsWith (javascript / typescript / java) / StartsWith (c#) / startswith (python) / str_starts_with (php) / strings.HasPrefix (golang)接口,求解《1455. 检查单词是否为句中其他单词的前缀》
顺序遍历,计数和奇偶性交换 2 种算法,求解《1417. 重新格式化字符串》
顺序遍历,计数和奇偶性交换 2 种算法,用双指针技巧,求解《1417. 重新格式化字符串》
顺序遍历,数字转字符串,求解《640. 求解方程》
顺序遍历,str / strconv.Itoa / sprintf(_, "x=%d", 1) / to_string 数字转字符串,求解《640. 求解方程》