给定 2 个字符串，仅删除一位数字以使 1 个字符串按字典顺序更小

Question

我正在尝试解决 Java 中字符串操作的编码问题。问题是

给定两个由数字和小写字母组成的字符串 S 和 T，您只能从任一字符串中删除一位数字，计算有多少种删除方式可以使 S 按字典顺序小于 T。

我自己想出了这个测试用例。如果 s = '3ab' 且 t = 'cd'，则返回 1。如果 s = '123ab' 且 t = '423cd'，则返回 6。

我的想法是使用 2 个 for 循环并通过检查字符是否为数字来遍历每个字符串，将其删除并与其他字符串进行比较。

private static int numSmaller(String s, String t){
    int ways = 0;

    for(int i = 0; i < s.length(); i++){
        StringBuilder sbs = new StringBuilder(s);
        if(Character.isDigit(s.charAt(i))){
            sbs.deleteCharAt(i);
            String sub = sbs.toString();
            if(sub.compareTo(t) < 0) {
                ways++;
            }
        }
    }

    for(int i = 0; i < t.length(); i++){
        StringBuilder sbt = new StringBuilder(t);
        if(Character.isDigit(t.charAt(i))){
            sbt.deleteCharAt(i);
            String sub = sbt.toString();
            if(s.compareTo(sub) < 0){
                ways++;
            }
        }
    }
    return ways;
}

正如你所看到的，空间复杂度非常糟糕，而且代码也显得多余。有没有办法优化这段代码？有没有人找到一种不使用字符串生成器或每次创建新字符串的方法？任何意见表示赞赏！

Answer 1

我使用streams长度为 10 的随机字符串将其与您的方法进行了比较。我运行了1 million这些字符串的测试用例，这两种方法提供了相同的结果。

流部分相当简单。我使用索引来根据数字位置IntStream构建字符串。substrings然后，我根据传递的BiFunctionlambda 进行过滤，该 lambda 充当两个参数谓词。对此进行筛选，我计算出成功的次数。

我这样做了两次，颠倒了参数和谓词逻辑，并对两个计数求和。

long count = count(s1, t1, (a, b) -> a.compareTo(b) < 0);
count += count(t1, s1, (a, b) -> b.compareTo(a) < 0);   

public static long count(String s, String t, BiFunction<String, String, Boolean> comp) {

      return IntStream.range(0, s.length()).filter(
        i -> Character.isDigit(s.charAt(i))).mapToObj(
              i -> s.substring(0, i) + s.substring(i + 1)).filter(
                    ss -> comp.apply(ss, t)).count();
}