字符串(2)

案例1
题目：

普通解法为二叉树遍历+匹配问题
考察t1中以每个节点为头的子树是否与t2一致。
若T1节点数为N，T2为M。
普通解法的时间复杂度为O(N*M)

最优解为二叉树序列化+KMP算法
时间复杂度为O(N+M)

案例2

分析：使用哈希表做字符计数

案例3
一个字符串，其前面任意部分挪到后面去形成的字符串叫做str的旋转词。比如str=“1234”，旋转词有“1234”、“2341”、“3412”、“4123”。给定两个字符串a和b，请判断a和b是否互为旋转词。
例子：
a=“1ab2”，b=“ab12”，返回false。
a=“2ab1”，b=“ab12”，返回true。
分析：若字符串长度为N，其最优解时间复杂度为O(N).
1.判断str1与str2是否相等
2.若长度相等，生成srt1+str1的大字符串。
3.用KMP算法判断大字符串中是否含有str2。

案例4
字符串单词逆序
“pig loves dog”逆序成“dog loves pig”

方法:
1.实现将字符串局部所有字符逆序的函数f
即首尾依次调序
例：”abcdef”变为“fedcba”
2.利用f将字符串所有字符逆序
“god sevol gip”
3.找到逆序后的字符串中每一个单词的区域，利用f将每一个单词的区域逆序。
“dog loves pig”

案例5
给定一个字符串str，和一个整数i。i代表str中的位置，将str[0…i]移到右侧，str[i+1…N-1]移到左侧。
举例：str=“ABCDE”，i=2。将str调整为“DEABC”。
要求，时间复杂度为O(N)，额外空间复杂度为O(1)。
分析：因为额外空间复杂度为O(1)，所以不能申请额外数组来调整，只能在原数组上调整。

此类题目，大部分思路：活用局部逆序。

案例6
字符串拼接，寻找一种拼接顺序，使其字典顺序中最小，并返回这个大字符串。

举例：
[“abc”，“de”]，拼接成“abcde”，也可拼接成“deabc”，但前者字典顺序更小，所以返回“abcde”

[“b”，“ba”]，拼接成“bba”，也可拼接成“bab
”，但后者字典顺序更小，所以返回“bab”

分析：若字符串数组长度为N，最优解时间复杂度O（N*logN），思路：选择正确排序方式。
比较str1和str2是错的，例子2可以证明

正解：若str1+str2