[알고리즘] Leetcode 392. Is Subsequence

개요

 

Is Subsequence - LeetCode

source 문자열 s와 target 문자열 t가 주어질 때 s가 t안에 순서대로 포함되어 있는지를 확인하는 문제였다

 

해결

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function (s, t) {
  if (s.length > t.length) return false;
  let index = -1;

  for (let i = 0; i < s.length; i++) {
    const check = index;
    for (let j = index + 1; j < t.length; j++) {
      if (s[i] === t[j]) {
        index = j;
        break;
      }
    }
    if (index === check) return false; // 찾지 못했다.
  }

  return true;
};

console.log(isSubsequence("ace", "abcde"));

index라는 변수를 따로 두어 문자열이 안에 포함되어 있는지 그리고 이전 문자열에 접근하지 않기 위해 따로 만들어 사용했다.

 

만약 문자열이 있으면 인덱스를 옮기고 인덱스가 안옮겨졌다면 문자가 없다는 것이니 false를 리턴한다.

 

더 깔끔한 코드

var isSubsequence = function(s, t) {
    // Base case: if the s string is empty...
    if(s.length == 0)
        return true;
    // Initialize pointers for both strings
    let i = 0;
    let j = 0;
    // We can iterate until either of them becomes zero...
    while(i < s.length && j < t.length){
        // Compare characters, increment i pointer...
        if(s.charAt(i) == t.charAt(j)){
            i++;
        }j++;
        // If the pointer is equal to the size of s, the match is found...
        if(i == s.length)  return true;
    }
    return false;       // Otherwise return false...
};

문자를 다 찾았으면 먼저 리턴해서 끝내고 만약 반복을 다 했다면 false를 리턴한다.

하나의 반복문에 조건도 간단해서 훨씬 쉬워보인다고 생각했다.