KMP 算法,求解《面试题 01.09. 字符串轮转》

例题

面试题 01.09. 字符串轮转

字符串轮转。给定两个字符串s1和s2,请编写代码检查s2是否为s1旋转而成(比如,waterbottle是erbottlewat旋转后的字符串)。
示例1:
输入:s1 = "waterbottle", s2 = "erbottlewat"
输出:True
示例2:
输入:s1 = "aa", s2 = "aba"
输出:False
提示:
字符串长度在[0, 100000]范围内。
说明:
你能只调用一次检查子串的方法吗?

答案

KMP 匹配算法

var isFlipedString = function(s1, s2) {
  return s1.length == s2.length && strstr(s1 + s1, s2)
};
const strstr = function(s, p) {
  const m = p.length, n = s.length, next = new Uint32Array(m)
  if (m === 0) return true 
  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
  }
  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 isFlipedString(s1: string, s2: string): boolean {
  return s1.length === s2.length && strstr(s1 + s1, s2)
};
function strstr(s: string, p: string): boolean {
  const m = p.length, n = s.length, next = new Uint32Array(m)
  if (m === 0) return true
  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
  }
  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
}
class Solution {
  function isFlipedString($s1, $s2) {
    return strlen($s1) === strlen($s2) && $this->strstr($s1 . $s1, $s2);
  }
  function strstr($s, $p) {
    $m = strlen($p);
    if ($m === 0) return true;
    $n = strlen($s);
    $next = array_fill(0, $m, 0);
    for ($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;
    }
    for ($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;
  }
}
func isFlipedString(s1 string, s2 string) bool {
  return len(s1) == len(s2) && strstr(s1 + s1, s2)
}
func strstr(s string, p string) bool {
  m, n := len(p), len(s)
  next := make([]int, m)
  if m == 0 {
    return true
  }
  for i, j := 1, 0; i < m; i++ {
    for j > 0 && p[i] != p[j] {
      j = next[j - 1]
    }
    if p[i] == p[j] {
      j++
    }
    next[i] = j
  }
  for i, j := 0, 0; i < n; i++ {
    for j > 0 && s[i] != p[j] {
      j = next[j - 1]
    }
    if s[i] == p[j] {
      j++
    }
    if j == m {
      return true
    }
  }
  return false
}
class Solution {
  public boolean isFlipedString(String s1, String s2) {
    return s1.length() == s2.length() && strstr(s1 + s1, s2);
  }
  public boolean strstr(String s, String p) {
    int m = p.length();
    if (m == 0) return true;
    int[] next = new int[m];
    for (int i = 1, j = 0; i < m; i++) {
      while (j > 0 && p.charAt(i) != p.charAt(j)) j = next[j - 1];
      if (p.charAt(i) == p.charAt(j)) j++;
      next[i] = j;
    }
    int n = s.length();
    for (int i = 0, j = 0; i < n; i++) {
      while (j > 0 && s.charAt(i) != p.charAt(j)) j = next[j - 1];
      if (s.charAt(i) == p.charAt(j)) j++;
      if (j == m) return true;
    }
    return false;
  }
}
public class Solution {
  public bool IsFlipedString(string s1, string s2) {
    return s1.Length == s2.Length && strstr(s1 + s1, s2);
  }
  public bool strstr(string s, string p) {
    int m = p.Length;
    if (m == 0) return true;
    int n = s.Length;
    int[] next = new 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;
    }
    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;
  }
}
bool myStrstr(char* s, char* p) {
  int m = strlen(p);
  if (m == 0) return true;
  int n = strlen(s);
  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;
  }
  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;
}
bool isFlipedString(char* s1, char* s2){
  int n1 = strlen(s1), n2 = strlen(s2);
  char* s = malloc(sizeof(char) * ((n1 << 1) + 1));
  sprintf(s, "%s%s", s1, s1);
  return n1 == n2 && myStrstr(s, s2);
}
class Solution {
public:
  bool isFlipedString(string s1, string s2) {
    return s1.size() == s2.size() && strstr(s1 + s1, s2);
  }
  bool strstr(string s, string p) {
    int m = p.size(), n = s.size();
    vector<int> next(m);
    if (m == 0) return true;
    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;
    }
    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;
  }
};
class Solution:
  def isFlipedString(self, s1: str, s2: str) -> bool:
    return len(s1) == len(s2) and self.strstr(s1 + s1, s2)

  def strstr(self, s: str, p: str) -> bool:
    m, n = len(p), len(s)
    next, j = [0] * m, 0
    if m == 0: return True
    for i in range(1, m):
      while j > 0 and p[i] != p[j]: j = next[j - 1]
      if p[i] == p[j]: j += 1
      next[i] = j
    j = 0
    for i in range(0, n):
      while j > 0 and s[i] != p[j]: j = next[j - 1]
      if s[i] == p[j]: j += 1
      if j == m: return True
    return False

原生 API

bool isFlipedString(char* s1, char* s2){
  int n1 = strlen(s1), n2 = strlen(s2);
  char* s = malloc(sizeof(char) * (n1 + n1 + 1));
  sprintf(s, "%s%s", s1, s1);
  return n1 == n2 && strstr(s, s2);
}
class Solution {
public:
  bool isFlipedString(string s1, string s2) {
    return s1.size() == s2.size() && (s1 + s1).find(s2) != string::npos;
  }
};

顺序遍历,求解《1790. 仅执行一次字符串交换能否使两个字符串相等》
顺序遍历,求解《1790. 仅执行一次字符串交换能否使两个字符串相等》
递归,分治,栈,顺序遍历深度,4 解法求解《856. 括号的分数》
递归,分治,栈,顺序遍历深度,4 解法求解《856. 括号的分数》
用哈希映射数据结构,分割字符串为数组,截取字符串,求解《811. 子域名访问计数》
用哈希映射数据结构,用 split / explode / stirngs.Split / strtok 分割字符串为数组,substring / substr / 指针截取字符串,求解《811. 子域名访问计数》