[LeetCode] 392. Is Subsequence - 자바스크립트

[ 문제 ]

leetcode.com/problems/is-subsequence/

Is Subsequence - LeetCode

---

[ 아이디어 ]

DP 문제라고 해서 풀어보고는 있는데 DP의 개념으로 풀기보다는 일반 정답을 맞추려는 목적으로 했다.#1 일반 풀이의 경우에도 시간복잡도가 크지 않다. substring의 문자열을 하나씩 비교하는데 mainstring에서 해당 문자열이 있나 확인하고 있을 때는 mainstring을 slice로 줄여가기 때문에 뒤로 갈수록 짧아진다. 만약 없다면 거기로 로직은 끝난다.근데 아무리 생각해도 이 문제는 substring 하나읽고 main에서도 읽고 다음 substring 읽고 main 읽는 식으로 하는게 가장 빠를것같다.

[ 코드 ]

// #1 일반 풀이
var isSubsequence = function (s, t) {
    let sIndex = 0;
    let tIndex = 0;
    let answer = false;
    while (tIndex >= 0) { // 해당 문자열이 없으면 순회 끝 false
        tIndex = t.indexOf(s[sIndex]); // substring의 값이 t에 있는지 확인
        if (tIndex >= 0) { // 있으면 
            t = t.slice(tIndex, t.length); // 해당 인덱스 전에 있는 문자열 버림
            sIndex++; // 다음 substring의 문자열을 향해
        } else {
            answer = false;
        }
        if (s.length == sIndex) { // 마지막까지 확인했는데 다 있으면 true
            answer = true;
            break;
        }
    }
    return answer;
};