1原题目
LeetCode_392
2 题目大意
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
3.题目分析

4基础知识
贪心算法，二分查找，双指针
4.1C的语法
4.2数据结构
4.3算法
贪心法（解法2）
把s的字符依次和t的字符匹配，匹配到s就下移，无论是否匹配，
t的下标都下移，匹配完s，说明s是t的子序列，否则不是。
时间O(max(M,N))

二分法（解法3）
对于挑战问题，对于相同的t，有10亿个s等待判断，每次都贪心去
匹配，效率就一般般了，还有更好的办法吗？

上面已经是线性的解法了，我们只能想logN的算法了，只有二分搜索。

二分搜索的前提是有序排列，这里没有有序排列，如何是好？

那就构造有序排列。字母a在t中出现的下标，可以是有序排列，
同样其他字母在t中出现的下标，分别都可以是有序排列。
这样就有26个有序排列了。

假如s[0]出现在了t的下标5，s[1]就必须在5之后，可以对s[1]这个字符
的所有下标进行查找刚好大于5的下标，既然是有序搜索，就可以是二分查找。

5解法
（1）简洁明了

int isSubsequence(char * s, char * t){while(true){if(!*s) return true;if(!*t) return false;if(*t++ == *s) s++;}
}

（2）贪心法（GO）

func isSubsequence(s string, t string) bool {i := 0for j := 0; j < len(t) && i < len(s); j++ {if s[i] == t[j] {i++}}return i >= len(s)
}

（3）二分法

func isSubsequence(s string, t string) bool {idxs := make([][]int, 26, 26)for i := 0; i < len(t); i++ {id := t[i] - 'a'idxs[id] = append(idxs[id], i)}target := -1for i := 0; i < len(s); i++ {ids := idxs[s[i]-'a']l, r := 0, len(ids)for l < r {mid := l + (r-l)/2if ids[mid] > target {r = mid} else {l = mid + 1}}//fmt.Println(s[i], l)if l < len(ids) && ids[l] > target {target = ids[l]} else {// 找不到符合的s[i]return false}}return true
}

6.总结