392题和贪心算法的关系
来源：10-1 贪心基础 Assign Cookies
zjg23
2020-03-30
看到这个题我首先想到的方法就是遍历s中的字符，去t中寻找是否存在。
这个方法和贪心算法的关系是什么，请您解惑。
public boolean isSubsequence(String s, String t) {
boolean res = true;
int curIndex = 0;
char[] tArr = t.toCharArray();
for(char cs:s.toCharArray()) {
boolean finded = false;
for(int i=curIndex;i<tArr.length;i++) {
if(tArr[i]==cs) {
finded = true;
curIndex = i + 1;
break;
}
}
if(!finded) {
res = false;
break;
}
}
return res;
}
写回答
1回答
-
比如在 s = aaaaaaaaaab 中寻找 t = ab。只要看到 s 的第一个字符是 a，和 t 的第一个字符 a 匹配上了，我们就可以放心地在 s 的后续中直接寻找 t 的后续了。
在 s 中看到的第一个和当前要匹配的字符一致，我们就可以“贪心地”直接匹配，而不用考虑后续的字符，所以这个问题可以叫贪心。
但其实，这种定义并不重要，在面试的时候，其实不会有人问你，这个问题对应的算法思想是什么。只要能解决问题就好：）
继续加油！：）
012020-03-31
