查找数据结构中所有好字符串的问题

17 Mar 2025 | 6 分钟阅读

问题陈述

给定长度为 n 的字符串 s1 和 s2，以及字符串 evil，返回好字符串的数量。好字符串的长度为 n，它在字典序上大于或等于 s1，小于或等于 s2，并且不包含 evil 作为子串。由于答案可能是一个非常大的数字，请返回模 10^9 + 7 的结果。

使用 HashMap 的 Java 方法

import java. util.*; 
public class GoodStringsFinder {
    static final int MOD = 1_000_000_000 + 7;
   //Create A HashMap with the name Index
    Map<String, Integer> index = new HashMap<>();
    HashMap[][][] memo;
    String A;
    String Z; 
    public int findGoodStrings(int n, String s1, String s2, String evil) {
        A = generate(n, 'a');
        Z = generate(n, 'z'); 
        memo = new HashMap[4][4][n + 1];
     //fill the hashmap with the required key values
       index.put(s1, 0);
        index.put(s2, 1);
        index.put(A, 2);
        index.put(Z, 3);
        return f(n, s1, s2, evil, Collections.emptyList());
    }
    private int f(int n, String s1, String s2, String evil, List<Integer> evilCandidates) {
        if (!evilCandidates.isEmpty() && evilCandidates.get(0) == evil.length()) {
            return 0;
        }	
       //if n equals 0, then we have to return 1
 if (n == 0) {
            return 1;
        }
        HashMap map = memo[index.get(s1)][index.get(s2)][n];
        String key = evilCandidates.toString();
     //if the map is not empty and the map has to contain the key, then we have to return the value of the key
   if (map != null && map.containsKey(key)) {
            return (int) map.get(key);
        }
        int k = s1.length() - n;
        long total = 0;
        char c1 = s1.charAt(k), c2 = s2.charAt(k);
        for (char s = c1; s <= c2; s++) {
            String left = s == c1 ? s1 : A;
            String right = s == c2 ? s2 : Z;     
List<Integer> nextEvil = new ArrayList<>();
            for (int c : evilCandidates) {
                if (s == evil.charAt(c)) {      
nextEvil.add(c + 1);
                }
            }
            if (s == evil.charAt(0)) {
                nextEvil.add(1);
            }
            total += f(n - 1, left, right, evil, nextEvil);
        }
        int res = (int) (total % MOD); 
        if (map == null) {
            map = new HashMap<>();
memo[index.get(s1)][index.get(s2)][n] = map;
        }
        map.put(key, res);
        return res;
    }
    static String generate(int count, char c) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < count; i++) {
sb.append(c);
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); 
System.out.println("Enter the length of the string:");
        int n = scanner.nextInt();
System.out.println("Enter the lower bound string:");
        String s1 = scanner.next();
System.out.println("Enter the upper bound string:");
        String s2 = scanner.next();
System.out.println("Enter the evil string:");
        String evil = scanner.next();
GoodStringsFinder finder = new GoodStringsFinder();
        int result = finder.findGoodStrings(n, s1, s2, evil); 
System.out.println("Number of good strings: " + result); 
scanner.close();
    }
}

输出

Find all good strings problem in Data Structure

代码解释

此 Java 代码实现了一个解决方案，用于查找给定范围内好字符串的数量并避免指定的 evil 字符串。它采用带备忘录的动态规划来高效地探索所有可能的组合。findGoodStrings 方法初始化必要的数据结构并启动递归。
f 方法处理子问题的递归探索和备忘录。它迭代字符串的每个位置上的所有字符，同时使用候选字符串列表跟踪 evil 字符串匹配情况。
generate 方法使用重复字符构建指定长度的字符串。最后，main 方法获取用户输入的字符串长度和边界，然后输出结果。

时间复杂度

findGoodStrings 方法的时间复杂度为 O(2(n * m^2 * s^2))，其中 n 是字符串的长度，m 是字母表中的字符数（此处为 26），s 是 evil 字符串的长度。
f 方法的时间复杂度为 O(n * m^2)，其中 n 是字符串的长度，m 是字母表中的字符数。

空间复杂度

空间复杂度为 O(n * s^2 * m)，其中 n 是字符串的长度，s 是字母表的大小，m 是 evil 字符串的长度。

缺点

然而，考虑到此选项的高空间复杂度，尤其是在处理巨大的输入时，可能存在更好的方法。通过使用变量长度数组来存储中间结果（memo）和另一个哈希表索引（index）来存储索引，可能会出现与大型输入相关的内存问题。
此外，具有此类算法的程序在输入字符串值相当大时可能会遇到堆栈溢出错误，因为每次递归调用都需要堆栈空间。因此，该解决方案为提供的动态规划工具提供了解决问题更有效的基础。

使用动态规划 + KMP 算法的 Java 方法

import java. util.Scanner; 
public class GoodStrings {
    Integer[][][][] dp;
    int mod = 1000000007;
    int[] lps; 
    // Function to compute the modular addition
    private int add(int a, int b) {
        return (a % mod + b % mod) % mod;
    }
    // Recursive function to find the count of good strings
    private int solve(char[] s1, char[] s2, int cur, boolean isStrictLower, boolean isStrictUpper, char[] evil, int evI) {
        // Base case: All characters in the evil string are matched
        if (evI == evil. length) return 0;
        // Base case: Reached the end of the string
        if (cur == s2.length) return 1;
        // Check if the value is already computed
        if (dp[cur][isStrictLower ? 1 : 0][isStrictUpper ? 1 : 0][evI] != null)
            return dp[cur][isStrictLower ? 1 : 0][isStrictUpper ? 1 : 0][evI]; 
        // Define the range for character comparison
        char start = isStrictLower ? s1[cur] : 'a';
        char end = isStrictUpper ? s2[cur] : 'z';
        int res = 0;
        // Iterate through the range of characters
        for (char ch = start; ch <= end; ch++) {
            if (evil[evI] == ch)
                res = add(res, solve(s1, s2, cur + 1, isStrictLower && ch == start, isStrictUpper && ch == end, evil, evI + 1));
            else {
                int j = evI;
                // Compute the Longest Prefix Suffix
                while (j > 0 && evil[j] != ch) j = lps[j - 1];
                if (ch == evil[j]) j++;
                // Recur with the updated prefix length
                res = add(res, solve(s1, s2, cur + 1, isStrictLower && ch == start, isStrictUpper && ch == end, evil, j));
            }
        }
        // Store and return the result
        return dp[cur][isStrictLower ? 1 : 0][isStrictUpper ? 1 : 0][evI] = res;
    }
    // Function to initialize and call the recursive function
    public int findGoodStrings(int n, String s1, String s2, String evil) {
        char[] arr = s1.toCharArray();
        char[] brr = s2.toCharArray();
        char[] crr = evil.toCharArray();
        // Compute the Longest Prefix Suffix array for evil string
        lps = new int[crr.length];
        for (int i = 1, j = 0; i < crr.length; i++) {
            while (j > 0 && crr[i] != crr[j]) j = lps[j - 1];
            if (crr[i] == crr[j]) lps[i] = ++j;
        }
        // Initialize the dp array
        dp = new Integer[n][2][2][crr.length];
        // Call the recursive function
        return solve(arr, brr, 0, true, true, crr, 0);
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); 
        // Input the length of strings and the strings themselves
System.out.print("Enter the length of strings n: ");
    //input the length n of the string size
    int n = scanner.nextInt();
   //input the string 1
System.out.print("Enter the first string s1: ");
        String s1 = scanner.next();
       //input the string 2
System.out.print("Enter the second string s2: ");
        String s2 = scanner.next();
       //input the evil string
System.out.print("Enter the evil string: ");
        String evil = scanner.next();
        // Create an instance of the Solution class
        Solution solution = new Solution();
        // Compute the count of good strings
        int result = solution.findGoodStrings(n, s1, s2, evil);
        // Output the result
System.out.println("Result: " + result); 
        // Close the scanner
scanner.close();
    }
}

输出

代码解释

此代码计算由两个字符串 s1 和 s2 定义的范围内的“好字符串”的数量。“好字符串”不包含任何与“evil 字符串”匹配的子串。它利用带备忘录的动态规划进行优化。
solve 函数递归地探索给定范围内的所有可能的字符组合，确保生成的每个字符串都不包含任何匹配 evil 字符串的子串。
为 evil 字符串计算最长前缀后缀（LPS）数组，以优化子串比较。
该解决方案考虑字符串中每个字符位置的下界和上界，从而有效地处理字符比较。

时间复杂度

时间复杂度为 O(n * m * k * l)，其中 n 是字符串长度，m 是 evil 字符串长度，k 是字母表大小，l 是递归调用的次数。

空间复杂度

空间复杂度为 O(n * k * k * m)，其中 n 是字符串长度，k 是字母表大小。

下一个主题从给定的机票列表中查找行程

查找数据结构中所有好字符串的问题

问题陈述

使用 HashMap 的 Java 方法

使用动态规划 + KMP 算法的 Java 方法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

查找数据结构中所有好字符串的问题

问题陈述

使用 HashMap 的 Java 方法

使用动态规划 + KMP 算法的 Java 方法

相关帖子

AVL 树的优点

循环双向链表的应用、优点和缺点

ArrayList vs LinkedList

回调队列

排序算法的应用、优点和缺点

Trie 的应用、优点和缺点

生成所有子数组

最小交换次数将二叉树转换为二叉搜索树

螺旋形式打印给定矩阵

替罪羊树

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器