首页 > 代码库 > 392. Is Subsequence
392. Is Subsequence
https://leetcode.com/problems/is-subsequence/#/solutions
http://www.cnblogs.com/EdwardLiu/p/6116896.html
public boolean isSubsequence(String s, String t) { int j = 0, i = 0; while (j < t.length() && i < s.length()) { if (s.charAt(i) == t.charAt(j)) { i++; j++; } else { j++; } } if (i == s.length()) { return true; } else { return false; } }
Follow Up:
The best solution is to create a map for String t, key is char, value is the index of appearance in ascending order
public boolean isSubsequence(String s, String t) { List<Integer>[] idx = new List[256]; // Just for clarity 字典集合, 每一个字母的ASCII 码当作键, 在t中的顺序当作值 for (int i = 0; i < t.length(); i++) { // 生成字典 if (idx[t.charAt(i)] == null) idx[t.charAt(i)] = new ArrayList<>(); idx[t.charAt(i)].add(i); } int prev = 0; // 前一个字母在t中的坐标, 控制升序 for (int i = 0; i < s.length(); i++) { //开始在字典里查找 if (idx[s.charAt(i)] == null) return false; // Note: char of S does NOT exist in T causing NPE int j = Collections.binarySearch(idx[s.charAt(i)], prev); //在当前字母表中查找其比之前的字母升序的坐标 if (j < 0) j = -j - 1; // 二分搜索的注意点 if (j == idx[s.charAt(i)].size()) return false; //在升序后找不到false prev = idx[s.charAt(i)].get(j) + 1; //在t中查找当前s的字母比s中的前一个字母在t中升序的坐标
}
return true;
}
392. Is Subsequence
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。