본문 바로가기
개발/알고리즘

[LeetCode] Repeated String Match (javascript)

by 자몬다 2021. 6. 11.
728x90

주어진 문자열 a, b가 있을 때,

a를 몇번 반복해야 b가 한번이라도 포함되는지 찾는 문제다.

 

처음엔 별생각 없이 str.includes(b) 대신 new RegExp(b).test(str) 를 사용해 풀었었다.

그러나 정규식보다 includes가 훨씬 빨랐다.

 

// 정규식보다 includes를 쓰는게 런타임도, 메모리도 훨씬 낫다
// 정규식 : Runtime 340ms, Memory 45MB
// includes : Runtime 84ms, Memory 40.4MB
/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 */
var repeatedStringMatch = function(a, b) {
    let str = a;
    let count = 1;
    while(!str.includes(b)){
        // 반복된 문자열이 a + b 길이보다 긴데도 찾을 수 없다면 존재하지 않는 것이다.
        if(str.length > a.length + b.length) return -1;
        str += a;  
        count++;
    }

    return count;
};

/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 */
var repeatedStringMatch = function(a, b) {
    let str = a;
    let count = 1;
    const regex = new RegExp(b);
    while(!regex.test(str)){
        // 반복된 문자열이 a + b 길이보다 긴데도 찾을 수 없다면 존재하지 않는 것이다.
        if(str.length > a.length + b.length) return -1;
        str += a;  
        count++;
    }

    return count;
};

 

 

 

 

https://leetcode.com/problems/repeated-string-match/

댓글0