JavaScript 알고리즘(8) Multiple Pointers Pattern - isSubsequence

 

 

차근차근 시간날 때마다 알고리즘을 풀고 있다. 

이번 하반기에는 좀더 집중해서 알고리즘을 공부할 생각이다.(선선포 후공부라 하자)

Multiple Pointers 패턴에서 isSubsequence 문제이다.

 

 

먼저 풀면서 느낀점은 우선 멀티 포인터를 쓰는 부분이 익숙하지 않았고,

2중 루프를 쓰지 않는다는 것 그래서 O(N) 으로 성능을 좀 더 개선시키는 방향으로 풀어보았다는 부분이었다.

어려웠지만 풀고나면 항상 성장하는 기분이 들어 뿌듯하다 😁

 

 

---

 

JavaScript 알고리즘(8) Multiple Pointers Pattern - isSubsequence

 

쉽게 한방에 설명해보겠다.

함수의 첫번째 인자로 주어진 'sing' 문자열과 두번째 인자로 주어진 'sting' 문자열이 있다.

두번째 문자열 sting 안에 첫번째문자열이 s i n g 순서 고대로 들어가 있으면 true 를  없으면 false 를 내뱉으면 된다.

 

 

 

각 인자들의 인덱스를 두개의 포인터로 삼아

while 문을 통해 각자의 인덱스 값을 비교하여 끝까지 검사하였다.

function isSubsequence(a, b) {
      let i = 0;
      let j = 0;
    
      while (b.length - 1 > j) {   // while total length of b is less than index [j],
        if (a[i] === b[j]) {       // if value of a[i] is equal to value of b[j]
          b.substr(j + 1);  	   // cut to b[j] among b
          i++;                     // add 1 to index [i]
          j = 0;                   // take intex [j] back to zero  
        
          if (i === a.length -1) { // if index [i] is equal of total length of a
            return true;	   // return true
          } 
        } else {                   // if not the same value between a[i] and b[j]
          j++;			   // add 1 to j
        }
      }
      
      return false;
}