[LeetCode] Number Of Matching Subsequences

문제링크

Number of Matching Subsequences - LeetCode

 

주어진 문자열 s를 통해 만들 수 있는 words 문자열의 개수를 구하는 문제
조건 : 꼭 연결된 문자열이 아니여도 된다.
(s = "abcde" words = ["ace"] 면 가능한 경우)

접근 방법

s = "abcde" word = "ace" 인 경우
s[i] === word[j] 일때 i++, j++;
s[i] !== word[j] 일때 i++;

두가지 조건으로 index값을 변경하며 진행하여 word.length === j 인 경우 true를 반환하는 함수를 작성하였다.

baseIndex = 0;
subIndex = 0;

while(baseIndex < baseStr.length && subIndex < subStr.length){
    if(baseStr[baseIndex] === subStr[subIndex]){
        baseIndex++;
        subIndex++;
    }else{
        baseIndex++;
    }
}​

하지만 아래와 같은 테스트 케이스를 통과하지 못했다.
s = "vvvvvvvvvvvvvvvvvvvvvvvvvvvv......vm" (길이 5000)
words = ["vm", "vm", "vm", "vm", "vm", "vm", "vm", "vm", "vm", "vm", "vm", "vm"...."vm"] (길이 5000)

if(baseStr.includes(subStr)) return true​

이를 해결하기 위해 위의 코드를 넣어도 시간초과가 발생하였다. (왜 발생하는지는 모르겠다..)

baseIndex를 끝까지 탐지하는 것이 문제라고 생각해서 고민하던 중 indexOf의 두번째 인자를 배워 사용하였다.

let cur = 0;
    
for(let subIndex = 0 ; subIndex < subStr.length; subIndex++){
    const baseIndex = baseStr.indexOf(subStr[subIndex], cur)
    if(baseIndex === -1){
        return false;
    }
    cur = baseIndex + 1;
}

return true;​

배운점 : indexOf의 두번째 인자는 그 위치부터 나머지까지 중 첫번째 인자의 index 번호를 찾는 것 이다.

s = "vvvvvvvvvvvvvvvvvvvvvvvvvvvv......vm" (길이 5000)
words = ["vm", "vm", "vm", "vm", "vm", "vm", "vm", "vm", "vm", "vm", "vm", "vm"...."vm"] (길이 5000)

범위 내에 값이 존재하면 해당 index번호를 return하고, 없으면 -1을 return한다.

이를 통해 모든 baseIndex를 순회하지 않아 효율성을 높힐 수 있었다.

참고 :  indexOf_MDN

 

처음 작성 코드(몇몇 케이스 미통과)
/**
 * @param {string} s
 * @param {string[]} words
 * @return {number}
 */
 var numMatchingSubseq = function(s, words) {
    let output = 0;
    
    words.forEach(word => {
        if(isIncludesWord(s, word)) output++;
    })
    
    return output;
};

const isIncludesWord = (baseStr, subStr) => {
    if(baseStr.includes(subStr)) return true
    
    baseIndex = 0;
    subIndex = 0;
    
    while(baseIndex < baseStr.length && subIndex < subStr.length){
        if(baseStr[baseIndex] === subStr[subIndex]){
            baseIndex++;
            subIndex++;
        }else{
            baseIndex++;
        }
    }
    
    return subIndex === subStr.length ? true : false;
}

 

// indexOf를 사용한 코드
/**
 * @param {string} s
 * @param {string[]} words
 * @return {number}
 */
 var numMatchingSubseq = function(s, words) {
    let output = 0;
    
    words.forEach(word => {
        if(isIncludesWord(s, word)) output++;
    })
    
    return output;
};

const isIncludesWord = (baseStr, subStr) => {
    let cur = 0;
    
    for(let subIndex = 0 ; subIndex < subStr.length; subIndex++){
        const baseIndex = baseStr.indexOf(subStr[subIndex], cur)
        if(baseIndex === -1){
            return false;
        }
        cur = baseIndex + 1;
    }
    
    return true;
}