LeetCode 1397: Find All Good Strings Solution

Master LeetCode problem 1397 (Find All Good Strings), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1397. Find All Good Strings

Hard

String Dynamic Programming String Matching

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming with memoization. We can define a recursive function that calculates the number of good strings based on the constraints given. We will keep track of the current position in the string, the prefix of the string that matches with the given prefix, and whether we have encountered the evil string as a substring.

At each step, we can recursively calculate the number of good strings based on the current position and other parameters. We can memoize the results to avoid redundant calculations.

Algorithm:

Define a recursive function dp(pos, match, isPrefix, isSuffix) that calculates the number of good strings based on the current position pos, whether the current prefix matches with the given prefix match, and whether the current string is a prefix or suffix of the evil string.
Initialize a memoization table memo to store the results of subproblems.
Iterate over the characters of the alphabet and make recursive calls to calculate the total number of good strings.
Return the result modulo 10^9 + 7.

Time Complexity:

The time complexity of this algorithm is O(n * m * 2 * 2), where n is the length of the strings and m is the length of the evil string.

Space Complexity:

The space complexity is O(n * m * 2 * 2) for memoization. :

Solution Code

class Solution {
    int mod = 1000000007;
    Integer[][][][] memo;

    public int findGoodStrings(int n, String s1, String s2, String evil) {
        memo = new Integer[n][evil.length()][2][2];
        return dp(0, 0, true, true, s1, s2, evil);
    }

    private int dp(int pos, int match, boolean isPrefix, boolean isSuffix, String s1, String s2, String evil) {
        if (match == evil.length()) return 0;
        if (pos == s1.length()) return 1;

        if (memo[pos][match][isPrefix ? 1 : 0][isSuffix ? 1 : 0] != null)
            return memo[pos][match][isPrefix ? 1 : 0][isSuffix ? 1 : 0];

        char start = isPrefix ? s1.charAt(pos) : 'a';
        char end = isSuffix ? s2.charAt(pos) : 'z';
        int res = 0;

        for (char c = start; c <= end; c++) {
            if ((isPrefix && c == s1.charAt(pos)) || (isSuffix && c == s2.charAt(pos))) {
                res = (res + dp(pos + 1, match + (c == evil.charAt(match) ? 1 : 0), isPrefix && c == s1.charAt(pos), isSuffix && c == s2.charAt(pos), s1, s2, evil)) % mod;
            } else {
                res = (res + dp(pos + 1, 0, isPrefix, isSuffix, s1, s2, evil)) % mod;
            }
        }

        return memo[pos][match][isPrefix ? 1 : 0][isSuffix ? 1 : 0] = res;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1397 (Find All Good Strings)?

This page provides optimized solutions for LeetCode problem 1397 (Find All Good Strings) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1397 (Find All Good Strings)?

The time complexity for LeetCode 1397 (Find All Good Strings) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1397 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1397 in Java, C++, or Python.

Back to LeetCode Solutions