给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1： 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2： 输入: "cbbd" 输出: "bb" 方法一：暴力法 很明显，暴力法将选出所有子字符串可能的开始和结束位置，并检验它是不是回文。 复杂度分析：时间复杂度：因为验证每个子字符串需要 O(n) 的时间，所以运行时间复杂度是 O(n^3)。空间复杂度：O(1)。 方法三：动态规划 为了改进暴力法...

1、BF算法 Brute Force，也就是暴力算法。从左往右依次匹配主串和模式串，若不符合则模式串位置往后移动一位，该算法思路很清晰，写法最简单，但是时间效率很低。假设主串的长度是m，模式串的长度是n，在极端情况下，BF算法的最坏时间复杂度是O（mn）。 2、RK算法 Rabin-Karp，比较字符串的哈希值。每一个字符串都可以通过某种哈希算法，转换成一个整型数，这个整型数就是hashcode。相比于BF算法，PK算法采用哈希值比较的方式，免去了许多无畏的字符比较，若模式串和主串哈希值相等，则再一个字符一个字符比较，时间复杂度提升为是O（n），但是若哈希冲突比较多，则RK算法就退化成了BF算...

字符串匹配与操作篇总结 0. 常见问题 1）从前往后容易会重复遍历，或者说重复移动，这时候可以考虑从后往前遍历，可能会减少遍历（移动）次数； 1. 字符串匹配算法 https://blog.nowcoder.net/n/c4edcbc44b3c43588876d6685b009409 2. 字符串重复问题 1）遍历。最容易想到的方法 一般使用两层for循环遍历，时间复杂度为O(n*n)；2）排序。对字符串排序，然后再判断是否有字符重复，需要O（nlogn)排序，然后再遍历一遍O(n)；⭐3）Parition。基于快速排序的partition，可以边排序边找重复，也即是每次partiti...