392题和贪心算法的关系

Question

看到这个题我首先想到的方法就是遍历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;
    }

Answer 1

liuyubobobo 2020-03-31 07:26:58

比如在 s = aaaaaaaaaab 中寻找 t = ab。只要看到 s 的第一个字符是 a，和 t 的第一个字符 a 匹配上了，我们就可以放心地在 s 的后续中直接寻找 t 的后续了。

在 s 中看到的第一个和当前要匹配的字符一致，我们就可以“贪心地”直接匹配，而不用考虑后续的字符，所以这个问题可以叫贪心。

但其实，这种定义并不重要，在面试的时候，其实不会有人问你，这个问题对应的算法思想是什么。只要能解决问题就好：）

继续加油！：）

• 提问者 zjg23 #1

  谢谢回答