跳到主要内容

1392.最长快乐前缀

链接：1392.最长快乐前缀
难度：Hard
标签：字符串、字符串匹配、哈希函数、滚动哈希
简介：给你一个字符串 s，请你返回它的 最长快乐前缀。

题解 1 - typescript​

  • 编辑时间：2021-10-13
  • 执行用时：96ms
  • 内存消耗：50.1MB
  • 编程语言：typescript
  • 解法介绍：kmp。
function getNext(str: string) {
  const next = [-1];
  for (let i = 1, j = -1; str[i]; i++) {
    while (j !== -1 && str[i] !== str[j + 1]) j = next[j];
    if (str[i] === str[j + 1]) j++;
    next[i] = j;
  }
  return next;
}
function longestPrefix(s: string): string {
  const next = getNext(s);
  const last = next[s.length - 1];
  return last === -1 ? '' : s.substring(0, last + 1);
}

题解 2 - typescript​

  • 编辑时间：2021-10-14
  • 执行用时：96ms
  • 内存消耗：49.9MB
  • 编程语言：typescript
  • 解法介绍：kmp。
function longestPrefix(s: string): string {
  const next = [-1];
  for (let i = 1, j = -1; s[i]; i++) {
    while (j !== -1 && s[i] !== s[j + 1]) j = next[j];
    if (s[i] === s[j + 1]) j++;
    next[i] = j;
  }
  return s.substring(0, next[s.length - 1] + 1);
}