算法：字符串和二分搜索相关题目

• 回文
• 子串(连续)、子序列(不连续)
• 前缀树（Trie树)、后缀树和后缀数组
• 匹配
• 字典序

1. 规则判断 判断字符串是否符合整数，浮点数 是否返回文本规则
2. 数字运算 与大整数相关的加、减、乘、除 操作
3. 与数组操作有关 排序技巧，快排划分技巧
4. 字符计数类型 hash表、依据ascii固定长度数组用于统计255、65535 常见的计数题类型:滑动窗口，寻找无重复子串，变位词
5. 动态规划 最长公共子串，最长公共子序列，最长回文子串，最长回文子序列
6. 搜索类型
7. 高级算法数据结构
   • 最长回文子串 manachar算法 马拉车算法
   • kmp 解决字符串匹配问题

# KMP算法 def build_prefix_table(text):     ‘构建前缀表’     prefix = [0]*len(text)     ptr = 0 #公共前缀指针     i = 1     n = len(text)     while i < n:         if text[i] == text[ptr]:             ptr  = 1             prefix[i] = ptr             i  = 1         else:             if ptr > 0:                 ptr = prefix[ptr-1]             else:                 prefix[i] = 0                 i  = 1     print(prefix)     i = n-1     while i>0:         prefix[i] = prefix[i-1]         i -= 1     prefix[0] = -1     print(prefix)     return prefix  pattern = 'ABABCABAA' build_prefix_table(pattern)

def kmp(pattern, text):
    n = len(pattern)
    m = len(text)
    prefix_table = build_prefix_table(pattern)

    i = 0 #pattern索引
    j = 0 #text索引
    while j < m:
        if i == n-1 and pattern[i] == text[j]: #找到匹配字符串
            print("founded at", j-i)
            i = prefix_table[i]
        elif i < n and pattern[i] == text[j]:
            i += 1
            j += 1
        elif i<n:
            i = prefix_table[i]
            if i == -1:
                i += 1
                j += 1

kmp("ABABCABAA","ABABABCABAABABAB")

- 前缀树、后缀树、后缀数组 问题 -- 通常面试极少出现

备注：Java中string类型不可更改，需要使用stringbuffer,stringBuilder或者toCharArray的操作

1. 给定彼此独立的两棵树头节点分别为t1和t2，判断t1中是否有与t2树拓扑结构完全相同的子树。 （判断t2是否是t1的子树？） 常规解法：二叉树遍历 + 匹配问题 O(N*M) leetcode 572 树的子树 树A是树B的子树有如下三种情况： 这两个树相等； 树A是树B左子树的子树； 树A是树B右子树的子树； 基于此进行二叉树的遍历加匹配 最优解: 二叉树序列化 + KMP算法 O(N+M) 注意这里的序列化必须加上表示空节点的None，否则无法实现真正的一一对应。 且序列化时必须保证树的头尾也有分割符，这样才能保证字符串匹配时不会出现问题。

2. 给定两个字符串 str1 和 str2 ，判断两个字符串是否互为变形词。 https://leetcode.cn/problems/dKk3P7/ 哈希表统计词频 C++ 固定大小数组统计词频 done

3. 给定两个字符串，判断这两个字符串是否互为旋转词。 str1和str2，str1+str1 其实穷举了所有旋转过程，然后使用kmp算法判断str2是否为str1的子串 https://www.nowcoder.com/questionTerminal/687deda2cc57473499e058207f6258cf https://leetcode.cn/problems/rotate-string/ done

4. 给定一个字符串，在单词间做逆序调整。 https://leetcode.cn/problems/fan-zhuan-dan-ci-shun-xu-lcof/ 利用python特征 done

5. 给定一个字符串str，以及整数i，请将str[0:i]移到右侧，str[i+1…N-1]移到左侧。要求时间复杂度O(N)，空间复杂度O(1)。 做三次逆序变换。 [0:i]内部做一次逆序；[i+1:N-1]内部做一次逆序 [0:N-1]内部统一做一次逆序

def reverseStr(str, i):
    charArr = list(str)
    n = len(charArr)
    reverse(charArr, 0, i-1)
    reverse(charArr, i, n-1)
    reverse(charArr, 0, n-1)
    print(charArr)

7. 给定一个字符串string，将其中所有空格字符替换成"%20"，假设str后有足够的空间 lc:https://leetcode.cn/problems/ti-huan-kong-ge-lcof/ nowcoder: 剑指offer 替换空格

8. 给定一个字符串string，判断是不是整体有效的括号字符串。 只需要维护一个统计变量，计算右括号与左括号数量的差值。

9. 给定一个字符串string，返回最长无重复字符串子串的长度。 最优：时间复杂度O（n），额外空间复杂度 O（n） 双指针：时间复杂度 O(n)，额外空间复杂度 O(字符串长度) lc第3题：https://leetcode.cn/problems/longest-substring-without-repeating-characters/

    def lengthOfLongestSubstring(self, s):
        """ :type s: str :rtype: int """
        if not s:
            return 0
        start = 0
        end = 1
        dic = { 
        s[0]:0}
        n = len(s)
        length = 1
        while end < n:
            if s[end] not in dic:
                dic[s[end]] = end
                length = max(length, end-start+1)
            else:
                last = dic[s[end]]
                start = max(last+1, start)
                length = max(length, end-start+1)
                dic[s[end]] = end
            end += 1
        return length