LeetCode - repeated string match

repeated string match

• Difficulty : easy

Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.

• A, B 2개의 문자열을 받고 최소 횟수로 반복하여 B 문자열이 A에 포함되는지 확인(포함되지 않으면 -1 반환)

example
For example, with A = "abcd" and B = "cdabcdab".
Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").

• cdabcdab 문자열이 포함되려면 A 문자열은 abcdabcdabcd 3번 반복되어야 하므로 3을 반환

Note:
The length of A and B will be between 1 and 10000.

solution

• 작성 언어 : javascript
• 처음에는 Rabin-Karp 알고리즘으로 접근을 하였으나, testcase에 밑에 무서운놈이 만족을 못한다.

Input:
"aaaaaaaaaaaaaaaaaaaaaab"
"ba"
Output:
-1
Expected:
2

// 초기코드

/**
 * @param {string} A
 * @param {string} B
 * @return {number}
 */
var repeatedStringMatch = function(A, B) {
    
};

var repeatedStringMatch = function(A, B) {
    
    let targetString = '';
    let repeatCount = 0;
    
    while(targetString.length <= (A.length + B.length)) {
        repeatCount++;
        targetString = A.repeat(repeatCount);
        
        if(targetString.includes(B)) {
            return repeatCount;
        }
        
    }
    
    return -1;
    
};

• 이거는 풀다가 빡쳐서 결국에는 다른 해결방법을 참조
• A 문자열, B 문자열 길이를 구해서 while 문 기저조건으로 사용
• 반복을 하는 문자열에 반복을 해주고 그전에 포함이 되면 반복횟수를 반환하고, while 문이 기저조건으로 나오면 최대한 반복을했으나 일치하는 문자가 없다는것이므로, -1 반환
• 해결책에 라빈카프 알고리즘이 설명되어 있어서 찾아서 해봤으나, ab ba => 2 이 조건에서 걸리기 때문에 짜증;(방법이 있을거다 내가 못해서 그렇지;;)
• 좀 단순하게 생각을 하는 연습도 필요한거 같다 ㅠㅠ

• 초기 삽질코드😱

var repeatedStringMatch = function(A, B) {
    
    if(B.includes(A) && A.length === B.length) {
        return 1;
    }
    
    if(A.includes(B)) {
        return 1;
    }
    
    let aHash = 0;
    let bHash = 0;
    
    A.split('').reverse().forEach((char, index) => {
        aHash += char.charCodeAt() * Math.pow(2, index);
    });
    
    B.split('').reverse().forEach((char, index) => {
        bHash += char.charCodeAt() * Math.pow(2, index);
    });

    
    if(aHash > bHash) {
        
        for(let i=0; i < A.length; i++) {
            const subString = A.substring(i, i + B.length);
            if(B.length != subString.length) {
                return -1;
            }
            let hashValue = 0;
            subString.split('').reverse().forEach((char, index) => {
                hashValue += char.charCodeAt() * Math.pow(2, index);
            });
            if(bHash === hashValue){
                break;
            }
        }
        
    } else {
        
        for(let i=0; i < B.length; i++) {
            const subString = B.substring(i, i + A.length);
            if(A.length != subString.length) {
                return -1;
            }
            let hashValue = 0;
            subString.split('').reverse().forEach((char, index) => {
                hashValue += char.charCodeAt() * Math.pow(2, index);
            });
            if(aHash === hashValue){
                break;
            }
        }
        
    }
  
    
    
    let repeatCount = 1;
    let tempA = A;
    while(true) {
            
        if(tempA.includes(B, 0)) {
            return repeatCount;
        } else {
            repeatCount++;
            tempA = A.repeat(repeatCount);
        }
        
    }
    
};

• 참조 : https://jackpot53.tistory.com/111
• 참조 : https://idea-sketch.tistory.com/24
• 라빈카프 알고리즘은 문자열을 수치(해쉬 값)로 변환해서 탐색하는 알고리즘
• 초기삽질코드는 ab ba -> 이 테스트케이스에서 걸린다..ㅠㅠ
• A : aaaba / B : ba 를 찾는다고 가정하면 이걸 숫자로 바꾼다 -> H = (A[0] * 2^1) + (A[1] * 2^0) -> H = (97 * 2^1) + (97 * 2^0)

aa = 291 이다.
ba = 293 이다.

• 문자열이 길면, H 값이 overflow 를 발생할 수 있다.(이를 위해, 모듈러 연산(%)을 한다)