diff options
-rw-r--r-- | find_all_good_strings.c | 80 | ||||
-rw-r--r-- | find_all_good_strings.py | 83 |
2 files changed, 163 insertions, 0 deletions
diff --git a/find_all_good_strings.c b/find_all_good_strings.c new file mode 100644 index 0000000..7190c0f --- /dev/null +++ b/find_all_good_strings.c @@ -0,0 +1,80 @@ +// 1397. Find All Good Strings +#include "leetcode.h" + +/* + * given the strings 's1' and 's2' of size 'n' and the string 'evil', return the + * number of good strings. a good string has size 'n', it is alphabetically + * greater than or equal to 's1', it is alphabetically smaller or less than + * 's2', and it does not contain the string 'evil' as a substring. since the + * answer can be a huge number, return this modulo 10^9+7. + */ + +static int mod = 1e9 + 7; + +int count_good_strings(char *s, int n, char *evil, int m, long long *dp) { + int sum = 0, i, k; + for (i = 0; i <= n - m; ++i) { + for (k = 0; k < m && s[i + k] == evil[k]; ++k) + ; + if (k == m) { + for (int j = i + k - 1; j >= i; --j) { + sum += (s[j] - 'a') * dp[n - j - 1]; + sum %= mod; + } + return sum - 1; + } + if (s[i + k] < evil[k]) + sum += (s[i] - 'a') * dp[n - i - 1]; + else + sum += dp[n - i] - ('z' + 1 - s[i]) * dp[n - i - 1]; + sum %= mod; + } + for (; i < n; ++i) { + sum += (s[i] - 'a') * dp[n - i - 1]; + sum %= mod; + } + return sum; +} + +int findGoodStrings(int n, char *s1, char *s2, char *evil) { + int m = strlen(evil), k = 0, i = 1; + long long *dp = (long long *)malloc((n + 1) * sizeof(long long)); + memset(dp, 0, m * sizeof(long long)); + while (i < m) { + if (evil[k] == evil[i]) + dp[i++] = ++k; + else if (k > 0) + k = dp[k - 1]; + else + ++i; + } + k = m - dp[m - 1]; + dp[0] = 1LL; + for (i = 1; i < m; ++i) + dp[i] = (dp[i - 1] * 26LL) % mod; + for (; i <= n; ++i) { + if (k == m) { + dp[i] = (dp[i - 1] * 26LL) % mod; + dp[i] -= dp[i - m]; + } else { + dp[i] = ((dp[i - 1] + dp[i - k - 1]) * 26LL) % mod; + dp[i] -= dp[i - m] + dp[i - k]; + } + } + int ans = count_good_strings(s2, n, evil, m, dp) - + count_good_strings(s1, n, evil, m, dp); + if (!strstr(s1, evil)) + ans++; + if (ans < 0) + ans += mod; + return ans % mod; +} + +int main() { + char *s11 = "aa", *s21 = "da", *e1 = "b"; + char *s12 = "leetcode", *s22 = "leetgoes", *e2 = "leet"; + char *s13 = "gx", *s23 = "gz", *e3 = "x"; + printf("%d\n", findGoodStrings(2, s11, s21, e1)); // expect: 51 + printf("%d\n", findGoodStrings(8, s12, s22, e2)); // expect: 0 + printf("%d\n", findGoodStrings(2, s13, s23, e3)); // expect: 2 +} diff --git a/find_all_good_strings.py b/find_all_good_strings.py new file mode 100644 index 0000000..48b64e1 --- /dev/null +++ b/find_all_good_strings.py @@ -0,0 +1,83 @@ +# 1397. Find All Good Strings +from string import ascii_lowercase + +""" +given the strings 's1' and 's2' of size 'n' and the string 'evil', return the +number of good strings. a good string has size 'n', it is alphabetically +greater than or equal to 's1', it is alphabetically smaller or less than +'s2', and it does not contain the string 'evil' as a substring. since the +answer can be a huge number, return this modulo 10^9+7. +""" + + +class Solution(object): + def prefix(self, s): + res = [0] * len(s) + for i in range(1, len(s)): + k = res[i - 1] + while k > 0 and s[k] != s[i]: + k = res[k - 1] + if s[k] == s[i]: + k += 1 + res[i] = k + return res[-1] + + def crete_connections(self, evil, t): + k = len(evil) + connections = [[-1] * t for _ in range(k)] + conn = [[] for _ in range(k)] + for i in range(k): + for letter in self.alphabet: + curr = self.prefix(evil + "#" + evil[0:i] + letter) + if curr != k: + connections[i][ord(letter) - ord("a")] = curr + if curr != 0: + conn[i].append([ord(letter) - ord("a"), curr]) + cnt = [[0] for _ in range(k)] + for i in range(k): + for j in range(1, t + 1): + cnt[i] += [cnt[i][-1] + (connections[i][j - 1] == 0)] + return cnt, conn + + def find_lesser_good(self, n, k, string, m, evil): + dp_bord = [[0] * k for _ in range(n)] + dp_notd = [[0] * k for _ in range(n)] + dp_bord[0][0] = 1 + for it_n in range(n - 1): + for it_k in range(k): + ord_num = ord(string[it_n + 1]) - ord("a") + for letter, s in self.con[it_k]: + dp_notd[it_n + 1][s] += dp_notd[it_n][it_k] + if letter < ord_num: + dp_notd[it_n + 1][s] += dp_bord[it_n][it_k] + dp_notd[it_n + 1][0] += self.con_numzero[it_k][-1] * dp_notd[it_n][it_k] + dp_notd[it_n + 1][0] += ( + self.con_numzero[it_k][ord_num] * dp_bord[it_n][it_k] + ) + dp_notd[it_n + 1] %= m + idx = self.prefix(evil + "#" + string[0 : it_n + 2]) + if idx != k and sum(dp_bord[it_n]) != 0: + dp_bord[it_n + 1][idx] = 1 + return sum(dp_bord[-1]) + sum(dp_notd[-1]) + + def findGoodStrings(self, n, s1, s2, evil): + """ + :type n: int + :type s1: str + :type s2: str + :type evil: str + :rtype: int + """ + self.alphabet = ascii_lowercase + m, k = 10**9 + 7, len(evil) + self.con_numzero, self.con = self.crete_connections(evil, len(self.alphabet)) + ans1 = self.find_lesser_good(n + 1, k, "#" + s2, m, evil) + ans2 = self.find_lesser_good(n + 1, k, "#" + s1, m, evil) + return (ans1 - ans2 + 1 - (evil in s1)) % m + + +if __name__ == "__main__": + obj = Solution() + print(obj.findGoodStrings(n=2, s1="aa", s2="da", evil="b")) + print(obj.findGoodStrings(n=8, s1="leetcode", s2="leetgoes", evil="leet")) + print(obj.findGoodStrings(n=2, s1="gx", s2="gz", evil="x")) |