1185. Fingerprint a Word
A spell checker stores a short numeric fingerprint for every word. For a lowercase word s, give each letter a value from 1 to 26 (a is 1, z is 26) and define the fingerprint as the sum of value(s[i]) * base^i over all positions i, taken modulo modulus. Position 0 is the first letter and carries base^0.
Return that fingerprint. The powers are far too large to compute directly, so evaluate the sum with Horner's rule, starting at the last character and moving to the first, reducing modulo modulus after every step. Intermediate products can pass 2^31, so use 64-bit arithmetic.
Constraints: 1 <= s.length <= 10^5, s is lowercase, and 2 <= base < modulus <= 10^9 + 7. The loop runs in O(n) time with O(1) extra space.
Example 1
- Input:
- s = "abc", base = 3, modulus = 100
- Output:
- 34
- Explanation:
The values are 1, 2, 3, so the hash is 1 + 2*3 + 3*9 = 34, and 34 mod 100 is 34.
Example 2
- Input:
- s = "zz", base = 10, modulus = 7
- Output:
- 6
- Explanation:
Both letters have value 26, so the hash is 26 + 26*10 = 286, and 286 mod 7 is 6.
Example 3
- Input:
- s = "a", base = 2, modulus = 3
- Output:
- 1
- Explanation:
A single letter a has value 1 and 1 mod 3 is 1.
Constraints
1 ≤ s.length ≤ 105
s is lowercase letters
2 ≤ base < modulus ≤ 109 + 7
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)