문제
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가 주어질때 문자열 t에 s가 포함되는지 물어보는 문제이다.
대신에 문자열 t에 있는 문자들은 연속되지 않더라도 순서만 유지되면 된다라는 조건이 있다.
생각의 흐름
참고로 문제를 잘못봐서 s와 t를 반대로 놓고 풀었다. 양해 부탁드립니다.
문자열 s의 길이는 최대 50만까지 가능하므로 절대 n2시간복잡도로 풀 수 없다고 생각했다. 그렇다면 O(n)으로 풀어야 한다는 얘긴데, t에 있는 문자열의 순서만 유지한채 s에 각 문자가 있는지 검사하면 될것같았다.
t의 순서가 s에서도 유지되어야 하기 떄문에, 0부터 끝까지 s와 t의 문자를 비교하면서 나아가면 될거라고 생각했는데 좀 더 효율적인 방법을 생각해보다가
양쪽에다 포인터를 두고 범위를 좁혀가도 어차피 똑같은 논리로 접근이 가능하겠다는 생각이 들었다. 왜냐면, 순서가 유지되어야 하기 떄문이다.
그래서 총 포인터 4개를 준비했고 t1과 t2는 s에 해당 문자가 있을때만 변화를 주었다.(그 문자 t[t1] t[t2]는 s안에 있다고 검증이 된 셈이니깐.)
검증이 모두 끝나거나(t1 > t2)
검증에 실패 한 경우(s1 > s2)
반복문이 종료되게 만들었다.
반복문이 종료된 시점에서 t1 > t2인 경우 t의 모든 문자가 검증되었다는 의미이므로 true를 리턴했다.
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isSubsequence = function(t, s) {
let s1 = 0,
t1 = 0,
s2 = s.length - 1,
t2 = t.length - 1;
while (s1 <= s2 && t1 <= t2) {
if (t[t1] == s[s1]) t1++;
if (t[t2] == s[s2]) t2--;
s1++;
s2--;
}
if (t1 > t2) return true;
else return false;
};결과
