主页 / coding / 问题 / 79295066
Accepted
CodeCrusader
Asked: 2024-12-20 00:59:51 +0800 CST

查找大于另一个字符串的子序列的数量

  • 772

给定两个长度为 m 的字符串 s 和另一个长度为 n 的字符串 t，计算 s 中有多少个子序列大于 t

如果序列 p 满足以下情况，则称其大于另一个序列 q：

a) 在 p 和 q 不同的第一个位置，p[i] > q[i]，或
b) |p| > |q| 且 q 是 p 的前缀（其中 |p| 表示密码 p 的长度）。

例子：

s="bab" t="ab"

结果= 5

解释：

Valid subsequences of s which are greater than t are
"b"
"ba"
"bb"
"bab"
"b"

限制： s 的长度为 1 到 10^5，t 的长度为 1 到 100

在有效组合的情况下，t 的长度可以大于 s 的长度。

我使用递归方法解决了这个问题，但时间复杂度为 O(2^n * n)。

public class Main {
    private static final int MOD = 1_000_000_007;

    private static void subsequence(String s, int index, String current, List<String> subsequences) {
        if (index == s.length()) {
            if (!current.isEmpty()) {
                subsequences.add(current);
            }
            return;
        }
        subsequence(s, index + 1, current, subsequences);
        subsequence(s, index + 1, current + s.charAt(index), subsequences);
    }

    private static boolean isGreater(String s1, String t) {
        int len1 = s1.length();
        int len2 = t.length();
        for (int i = 0; i < Math.min(len1, len2); i++) {
            if (s1.charAt(i) > t.charAt(i)) {
                return true;
            } else if (s1.charAt(i) < t.charAt(i)) {
                return false;
            }
        }
        return len1 > len2;
    }

    public static int solve(String s, String t) {
        List<String> subsequences = new ArrayList<>();
        subsequence(s, 0, "", subsequences);

        int count = 0;
        for (String e : subsequences) {
            if (isGreater(e, t)) {
                count = (count + 1) % MOD;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        System.out.println(solve("aba", "ab")); // Expected: 3
        System.out.println(solve("bab", "ab")); // Expected: 5
        System.out.println(solve("wrrmkhds", "bebbjvcgzlwtbvasphvm")); // Expected: 255
        System.out.println(solve("o", "h"));   // Expected: 1
    }
}

如何以较少的时间复杂度解决这个问题？

java

2 个回答

  1. 似乎您可以创建一个辅助列表，其中包含小于的字母的索引t[i]。将此列表称为x。

    然后使用简单的数学来确定使用索引之间的范围可以形成多少个子序列x。

    在您的示例中，x=[1]。因此，我们有第一个[0-0]可以形成1子序列的封闭范围。第二个范围是[2-2]，这为我们提供了范围[0-2]。您可以形成3C1+3C2+3C3=6子序列，但您必须减去[0-0]（已计算） 和[1-1]（未包括） 的子序列。因此，这为我们提供了1+4=5子序列。

    • 1
  2. Best Answer

    您可以使用递归关系，并通过动态规划来实现它。

    如果我们考虑一个从索引 𝑖 开始的 𝑠后缀和一个从索引 𝑗 开始的 𝑡后缀（我们对这些后缀使用符号 𝑠[𝑖:] 和 𝑡[𝑗:]），那么我们要解决的问题就比较小了，即第一个后缀有多少个子序列大于第二个后缀。我们可以将此结果用于更大的问题。

    如果我们想知道 𝑠[𝑖:] 和 𝑡[𝑗:] 的解决方案，那么我们有几种情况：

    • 如果 𝑠[𝑖:] 为空（即 𝑖 ≥ 𝑚），则有 0 个子序列。

    • 否则，我们可以将子序列的数量分成两组：

      1. 排除𝑠[𝑖]的子序列

        此计数等于 𝑠[𝑖+1:] 和 𝑡[𝑗:] 的解（我们只是从输入中删除了 𝑠[𝑖]）

      2. 包含𝑠[𝑖]的子序列

        • 如果 𝑗 ≥ 𝑛 或 𝑠[𝑖] > 𝑡[𝑗]，则 𝑡 的后续字符不再重要，我们可以自由选择包含或不包含 𝑠[𝑖+1:] 中的哪些字符。这表示 2 𝑚-1-𝑖个可能的子序列，所有子序列均以 𝑠[𝑖] 开头。

        • 当 𝑠[𝑖] = 𝑡[𝑗] 时，子序列的数量由 𝑠[𝑖+1:] 和 𝑡[𝑗+1:] 的解给出

        • 否则（当 𝑠[𝑖] < 𝑡[𝑗] 时），我们做出了无效的选择，因此对于这种情形，有 0 个子序列需要计数。

    更正式地，将 𝑚 定义为 𝑠 的长度，𝑛 定义为 𝑡 和 𝑇 𝑖 的长度，𝑗定义为 𝑠[𝑖:] 中大于 𝑡[𝑗:] 的子序列的数量。然后：

    • 当 𝑖 ≥ 𝑚 时， 𝑇 𝑖，𝑗 = 0

    • 𝑇 𝑖, 𝑗 = 𝑇 𝑖+1, 𝑗 + 2 𝑚-1-𝑖，否则 𝑗 ≥ 𝑛 或 𝑠[𝑖] > 𝑡[𝑗]

    • 𝑇 𝑖, 𝑗 = 𝑇 𝑖+1, 𝑗 + 𝑇 𝑖+1, 𝑗+1，否则 𝑠[𝑖] = 𝑡[𝑗]

    • 𝑇 𝑖, 𝑗 = 0，否则

    最后，我们需要 𝑇 0, 0的值

    为了实现这一点，我们可以使用自下而上的方法，从 𝑠 的空后缀开始（即 𝑖 = 𝑚），然后增加该后缀（减少 𝑖）。对于每个后缀，考虑 𝑗 从 𝑛 减少到 0。由于 𝑇 𝑖、𝑗仅直接依赖于 𝑇 𝑖+1、𝑗和 𝑇 𝑖+1、𝑗+1，我们实际上不需要存储整个矩阵 𝑇，只需将该矩阵的两行连续保存在内存中即可。

    以下是一个实现：

        public static int solve(String s, String t) {
        int m = s.length();
        int n = t.length();
        
        int[] dp = new int[n+1];
        int[] dpPrev;
        
        for (int i = m - 1; i >= 0; i--) { // Grow the suffix of s that is considered
            // Take a copy to have a reference to previous results (for smaller s suffix)
            dpPrev = dp.clone(); 
            // There are 2^(length of s[i:]) - 1 non-empty subsequences 
            //     when t[j:] is empty (j == n):
            dp[n] = 2 * dp[n] + 1;
            // Add the cases where s[i] is included in the subsequences
            for (int j = n - 1; j >= 0; j--) {
                int cmp = Character.compare(s.charAt(i), t.charAt(j));
                       // Add the count of all subsequences of s[s+1:] (+1 for empty one)
                dp[j] += cmp >  0 ? dpPrev[n] + 1 
                       // Add the count of subsequences of s[i+1:] greater than t[j+1:]
                       : cmp == 0 ? dpPrev[j+1]
                       : 0;
            }
        } 
        return dp[0];
    }

    注意：您的代码中有一个常数 1_000_000_007，而您的问题中没有提到这个常数。我认为您可以毫无问题地加入与该常数相关的要求。我宁愿不提它，以便将注意力集中在问题上。

    • 1

相关问题