資訊專欄INFORMATION COLUMN
摘要：題目要求如何判斷字符串是否是字符串的一個(gè)子序列。子序列是指中的字母均按照相對位置存在于中，比如是的一個(gè)子序列，但是就不是的一個(gè)子序列。可以看到我們能夠找到一個(gè)合法的序列，使得當(dāng)前字母的起始下標(biāo)始終大于上一個(gè)字母的下標(biāo)。
題目要求
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的一個(gè)子序列。子序列是指s中的字母均按照相對位置存在于t中，比如"abc"是"ahbfdc"的一個(gè)子序列，但是"axc"就不是"ahbgdc"的一個(gè)子序列。
思路一：java APIjava中提供了一個(gè)String.indexOf(char c, int startIndex)的方法，這個(gè)方法是指從字符串中的startIndex位置開始往后找，返回第一個(gè)c所在的下標(biāo)，如果找不到，則返回-1。利用這個(gè)方法我們可以快速的解決這個(gè)問題。
public boolean isSubsequence(String s, String t) {
if(s==null || s.length()==0) return true;
int start = -1;
for(int i = 0 ; i
思路二：二分法
二分法的思路主要是指，首先我們遍歷字符串t，找到每個(gè)字符在t中出現(xiàn)的位置。當(dāng)我們知道每個(gè)字符在t中出現(xiàn)的所有下標(biāo)后，就開始遍歷s，并開始找到距離上一個(gè)字符所在的位置之后的當(dāng)前字符的最小下標(biāo)。
舉例：
s="abc"
t="acbgbc"
遍歷t之后可以得到這樣一個(gè)字段：
a:{0}
b:{2,4}
g:{3}
c:{1,5}
之后遍歷s，并用一個(gè)index來記錄當(dāng)前字符所在的下標(biāo)，index初始時(shí)為-1。
s[0] = a, a:{0} -> index = 0
s[1] = b, b:{2,4} -> index = 2
s[2] = c, c:{1,5} -> index=5
可以看到我們能夠找到一個(gè)合法的序列，使得當(dāng)前字母的起始下標(biāo)始終大于上一個(gè)字母的下標(biāo)。
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;
}
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.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) ...
摘要：再用二分法找當(dāng)前值應(yīng)該在排好序的數(shù)組中的插入位置。因?yàn)橐业氖亲铋L的序列，所以每次將排好序的數(shù)組中替換成已經(jīng)排好序的，會(huì)能保證得到的結(jié)果是最長的。保證升序相等也要替換這個(gè)值 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...
摘要：題目要求扭動(dòng)序列是指數(shù)組中的相鄰兩個(gè)元素的差保證嚴(yán)格的正負(fù)交替，如數(shù)組中相鄰兩個(gè)元素的差為，滿足扭動(dòng)序列的要求?，F(xiàn)在要求從一個(gè)數(shù)組中，找到長度最長的扭動(dòng)子序列，并返回其長度。即前一個(gè)元素和當(dāng)前元素構(gòu)成下降序列，因此代碼如下 題目要求 A sequence of numbers is called a wiggle sequence if the differences between ...
