Missing Test Case - 3045. Count Prefix and Suffix Pairs II #20460
Description
LeetCode Username
b03201008
Problem number, title, and link
- Count Prefix and Suffix Pairs II https://leetcode.com/problems/count-prefix-and-suffix-pairs-ii/
Category of the bug
- Missing test Case (Incorrect/Inefficient Code getting accepted because of missing test cases)
Description of the bug
Code that uses fixed base and mod in hashing got "Accepted" verdict, while there are many tests when collision happens.
Language used for code
Python3
Code used for Submit/Run operation
MOD = (10**9) + 7
class RollingHash:
def __init__(self, base = 256, mod = MOD):
self.base = base
def update(self, old_hash, char):
return (old_hash * self.base + ord(char)) % MOD
def update2(self, old_hash, char, old_length):
return (pow(self.base,old_length,MOD)*ord(char) + old_hash) % MOD
def hash(self, string):
h = 0
for i in range(len(string)):
h = self.update(h, string[i])
return h
class Solution:
def countPrefixSuffixPairs(self, words: List[str]) -> int:
ans = 0
mapp = Counter()
rl = RollingHash()
for i in words:
pre = 0
post = 0
for j in range(len(i)):
pre = rl.update(pre, i[j])
post = rl.update2(post, i[-1-j], j)
if pre == post and pre in mapp:
ans += mapp[pre]
mapp[rl.hash(i)] +=1
return ans
Expected behavior
When
words =
["dmftst","zawakz"]
the expected answer is 0, but the code outputs 1.
Screenshots
