前言
这道题的实现方法有很多，包括dp，贪心算法，二分搜索，普通实现等等。
题目
Given a string s and a string t, check if s is subsequence of t.
You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).
Example 1:
s = "abc", t = "ahbgdc"
Return true.
Example 2:
s = "axc", t = "ahbgdc"
Return false.
Follow up:
If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?
题意说的是，判断字符串s是否是字符串t的字串（要求按照s中字符的顺序！）
实现
//
// Is Subsequence.cpp
// LeetCodeCppPro
//
// Created by George on 17/3/2.
// Copyright © 2017年 George. All rights reserved.
//
#include <stdio.h>
#include "PreLoad.h"
class Solution {
public:
/**
* 两个节点，贪心算法的思想
*
* @param s <#s description#>
* @param t <#t description#>
*
* @return <#return value description#>
*/
bool isSubsequence(string s, string t) {
if (s == t || (s == "" && t.length() > s.length())) {
return true;
}
else if (s.length() > t.length()) {
return false;
}
int idx = 0;
for (int i = 0; i < s.length(); i++,idx++) {
while (idx < t.length() && t[idx] != s[i]) {
idx++;
}
if (idx >= t.length()) {
return false;
}
}
return true;
}
/**
* two point
* 失败，没调试好
*
* @param s <#s description#>
* @param t <#t description#>
*
* @return <#return value description#>
*/
bool isSubsequence2(string s, string t) {
if (s == t || (s == "" && t.length() > s.length())) {
return true;
}
else if (s.length() > t.length() || (s.length() == t.length() && s != t)) {
return false;
}
int s_left = 0, s_right = s.length()-1;
int t_left = 0, t_right = t.length()-1;
while (t_left < t_right) {
while (s[s_left] != t[t_left] && t_left < t_right) {
t_left++;
}
while (s[s_right] != t[t_right] && t_left < t_right) {
t_right--;
}
if (t_left == t_right) {
if (s[s_left] == t[t_left]) {
return true;
}
else {
return false;
}
}
if (s[s_left] == t[t_left]) {
s_left++;
t_left++;
}
else {
t_left++;
}
if (s[s_right] == t[s_right]) {
s_right--;
t_right--;
}
else {
t_right--;
}
if (t_left == t_right) {
if (s[s_left] == t[t_left]) {
return true;
}
else {
return false;
}
}
}
if (t_left >= t_right) {
return false;
}
else {
return true;
}
}
/**
* 使用hash，取idx递增顺序
*
* @param s <#s description#>
* @param t <#t description#>
*
* @return <#return value description#>
*/
bool isSubsequence3(string s, string t) {
vector<vector<int>> sequence(26);
// 纪录下每个单词出现的下标
for (int i = 0; i < t.length(); i++) {
int idx = t[i] - 'a';
sequence[idx].push_back(i);
}
// 根据s的单词顺序
int preIndex = -1;
for (int i = 0; i < s.length(); i++) {
int idx = s[i] - 'a';
auto nums = sequence[idx]; //取得字符的下标集合
if (nums.empty()) {
return false;
}
auto itr2 = nums.begin();
while (itr2 != nums.end() && *itr2 <= preIndex) {
itr2++;
}
if (itr2 == nums.end()) {
return false;
}
else {
preIndex = *itr2;
}
}
return true;
}
/**
* 和上面的思想类似，
* 不同的是使用了一个数组index记录下同一个单词的次数，读取更加方便
*
* @param s <#s description#>
* @param t <#t description#>
*
* @return <#return value description#>
*/
bool isSubsequence4(string s, string t) {
vector<vector<int>> posMap(26); // 题目已经假设是小写字母
// 纪录目标字符串t中字符的出现次数
for (int i = 0; i < t.length(); i++) {
posMap[t[i] - 'a'].push_back(i);
}
int pre = -1;
int index[26]; //纪录s中每个单词出现的个数，为后面取该字符的下标做准备，避免从头开始遍历
memset(index, -1, sizeof(index));
for (int i = 0; i < s.length(); i++) {
int j = s[i] - 'a';
index[j]++;
// posMap[j][index[j]] 为取某个字符的下标
while (index[j] < posMap[j].size()) {
if (posMap[j][index[j]] > pre) { //直到取得比上一个字符的下标大的下标值
break;
}
++index[j];
}
if (index[j] > posMap[j].size()) {
return false;
}
pre = posMap[j][index[j]]; //更新为当前字符的下标
}
return true;
}
/**
* 思路和前面的一样，都使用了之前的下标
* 不同的是做法更佳简洁，因为使用了upper_bound函数
*
* @param s <#s description#>
* @param t <#t description#>
*
* @return <#return value description#>
*/
bool isSubsequence5(string s, string t) {
vector<vector<int>> record(26);
for (int i = 0; i < t.size(); i++) {
record[t[i] - 'a'].push_back(i);
}
int index = -1;
for (int i = 0; i < s.size(); i++) {
int idx = s[i] - 'a';
auto itr = upper_bound(record[idx].begin(), record[idx].end(), index);
if (itr == record[idx].end()) {
return false;
}
index = *itr;
}
return true;
}
/**
* 和第一种思想类似
*
* @param s <#s description#>
* @param t <#t description#>
*
* @return <#return value description#>
*/
bool isSubsequence6(string s, string t) {
if (s.length() == 0) {
return true;
}
queue<int> queue; //使用队列可以保证字符的处理顺序是正确的
for (char c : s) queue.push(c);
for (int i = 0; !queue.empty() && i < t.length(); i++) {
if (t[i] == queue.front()) {
queue.pop();
}
}
return queue.empty();
}
/**
* dp实现
* 不同点在于，只使用了两行数据，节省空间
* 使用了之后到的数据覆盖之前的数据
*
* @param s <#s description#>
* @param t <#t description#>
*
* @return <#return value description#>
*/
bool isSubsequence7(string s, string t) {
if (s.length() == 0) {
return true;
}
else if (t.length() != 0) {
return false;
}
int m = t.length(), n = s.length();
vector<vector<bool>> dp(2, vector<bool>(n+1, false));
// 设置第一行，因为只需要看s的数据
for (int i = 0; i <= n; i++) {
dp[0][i] = true;
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (t[i] == s[j]) {
dp[1][j+1] = dp[0][j];
}
else {
dp[1][j+1] = dp[1][j];
}
}
// 进行覆盖，将第1行数据覆盖到第0层数据上，循环使用
for (int j = 0; j < n; j++) {
dp[0][j] = dp[1][j];
}
}
return dp[1][n];
}
/**
* 正儿八经的使用dp
*
* @param s <#s description#>
* @param t <#t description#>
*
* @return <#return value description#>
*/
bool isSubsequence8(string s, string t) {
if (s.length() == 0) {
return true;
}
else if (t.length() != 0) {
return false;
}
int m = t.length(), n = s.length();
vector<vector<bool>> dp(m, vector<bool>(n, false));
if (s[0] == t[0]) {
dp[0][0] = true;
}
// 将第一列的数据置为false，因为不需要
for (int i = 1; i < m; i++) {
dp[i][0] = false;
}
// 第一行数据
for (int i = 1; i < n; i++) {
dp[0][i] = dp[0][i-1] || s[i] == t[0];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (t[i] == s[j]) {
dp[i][j] = dp[i-1][j-1] || dp[i][j-1];
// 将该行上的数据都置为true
if (dp[i][j]) {
for (int k = j+1; k < n; k++) {
dp[i][k] = true;
}
continue;
}
}
}
}
return dp[m-1][n-1];
}
void test() {
string s = "aaaabc", t = "llallllbllllc";
if (isSubsequence3(s, t)) {
cout << "true" << endl;
}
else {
cout << "false" << endl;
}
}
};