[Rolling Hash] Shortest Palindrome

https://leetcode.com/problems/shortest-palindrome/description/?envType=daily-question&envId=2024-09-20

 

 

 

 

 

✨ 인사이트

Hash를 사용해서 두 문자열이 같은지 판단하는 방법도 있을 것이다. (Palindrome임을 판단하기 위해서 원래 문자열과 뒤집어진 문자열이 같은지 확인할 때 Hash)가 사용된다. 그런데 Hash를 그대로 사용하면 시간이 오래 걸리기 때문에 Rolling Hash를 사용할 수 있다. Sliding Window 방식 중 하나다.

 

새로운 문자열로 넘어갈 때 사라지는 문자 하나를 빼고 추가한 문자열을 더하면 매번 해시값을 통째로 구해야 하는 어려움을 피할 수 있다.

 

 

 

 

✨ 인사이트 - Rolling Hash

base를 29, mod를 10^9 + 7로 지정하고 구해보자.

 

 

그전에 왜 이 숫자들이 선택됐는지 알아보자.

 

base가 29인 이유는 영어 알파벳이 26개이기 때문에 이보다 큰 소수를 사용했다. 이보다 작으면 알파벳의 값이 자릿수를 넘어버리는 불상사가 발생하고 또 너무 커버리면 계산량이 많아지기 때문에 26보다 큰 가장 작은 소수 29를 택했다.

 

mod를 넣는 이유는 해시값이 너무 커지는 것을 방지하기 위해서다. 그렇다고 이 값이 너무 작아버리면 서로 다른 해시값이 같아질 수 있기 때문에 적당히 큰 값으로 했다. 게다가 10^9 + 7은 소수이기 때문에 나머지가 고르게 분배된다.

 

 

 

 

 

✅ 정답

Time Complexity: O(n)
Space Complexity: O(n)

 

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        hash_base = 29
        mod_value = int(1e9 + 7)
        forward_hash = 0
        reverse_hash = 0
        power_value = 1
        palindrome_end_index = -1

        # Calculate rolling hashes and find the longest palindromic prefix
        for i, current_char in enumerate(s):
            # Update forward hash
            forward_hash = (
                forward_hash * hash_base + (ord(current_char) - ord("a") + 1)
            ) % mod_value

            # Update reverse hash
            reverse_hash = (
                reverse_hash + (ord(current_char) - ord("a") + 1) * power_value
            ) % mod_value
            power_value = (power_value * hash_base) % mod_value

            # If forward and reverse hashes match, update palindrome end index
            if forward_hash == reverse_hash:
                palindrome_end_index = i

        # Find the remaining suffix after the longest palindromic prefix
        suffix = s[palindrome_end_index + 1 :]

        # Reverse the remaining suffix
        reversed_suffix = suffix[::-1]

        # Prepend the reversed suffix to the original string and return the result
        return reversed_suffix + s