資訊專欄INFORMATION COLUMN
摘要：題目要求如何判斷字符串是否是字符串的一個子序列。子序列是指中的字母均按照相對位置存在于中，比如是的一個子序列，但是就不是的一個子序列。可以看到我們能夠找到一個合法的序列，使得當前字母的起始下標始終大于上一個字母的下標。
題目要求
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中的字母均按照相對位置存在于t中，比如"abc"是"ahbfdc"的一個子序列，但是"axc"就不是"ahbgdc"的一個子序列。
思路一：java APIjava中提供了一個String.indexOf(char c, int startIndex)的方法，這個方法是指從字符串中的startIndex位置開始往后找，返回第一個c所在的下標，如果找不到，則返回-1。利用這個方法我們可以快速的解決這個問題。
public boolean isSubsequence(String s, String t) {
if(s==null || s.length()==0) return true;
int start = -1;
for(int i = 0 ; i
思路二：二分法
二分法的思路主要是指，首先我們遍歷字符串t，找到每個字符在t中出現的位置。當我們知道每個字符在t中出現的所有下標后，就開始遍歷s，并開始找到距離上一個字符所在的位置之后的當前字符的最小下標。
舉例：
s="abc"
t="acbgbc"
遍歷t之后可以得到這樣一個字段：
a:{0}
b:{2,4}
g:{3}
c:{1,5}
之后遍歷s，并用一個index來記錄當前字符所在的下標，index初始時為-1。
s[0] = a, a:{0} -> index = 0
s[1] = b, b:{2,4} -> index = 2
s[2] = c, c:{1,5} -> index=5
可以看到我們能夠找到一個合法的序列，使得當前字母的起始下標始終大于上一個字母的下標。
public boolean isSubsequence(String s, String t) {
List[] idx = new List[256]; // Just for clarity
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;
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;
prev = idx[s.charAt(i)].get(j) + 1;
}
return true;
}
想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/72719.html
Problem 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) ...
摘要：再用二分法找當前值應該在排好序的數組中的插入位置。因為要找的是最長的序列，所以每次將排好序的數組中替換成已經排好序的，會能保證得到的結果是最長的。保證升序相等也要替換這個值 LeetCode[300] Longest Increasing Subsequence Given an unsorted array of integers, find the length of longe...
Problem Given an unsorted array of integers, find the length of longest increasing subsequence. Example: Input: [10,9,2,5,3,7,101,18]Output: 4 Explanation: The longest increasing subsequence is [2,3,7...
Problem Given strings S and T, find the minimum (contiguous) substring W of S, so that T is a subsequence of W. If there is no such window in S that covers all characters in T, return the empty string...
摘要：題目要求扭動序列是指數組中的相鄰兩個元素的差保證嚴格的正負交替，如數組中相鄰兩個元素的差為，滿足扭動序列的要求。現在要求從一個數組中，找到長度最長的扭動子序列，并返回其長度。即前一個元素和當前元素構成下降序列，因此代碼如下 題目要求 A sequence of numbers is called a wiggle sequence if the differences between ...
