2

我正在尝试解决 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;
}

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

4

5 回答 5

1

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

流部分相当简单。我使用 anIntStream来索引字符串以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();
}
于 2019-08-26T03:51:29.797 回答
0

您可以将时间复杂度降低到 O(m+n)，其中 m,n 是 S 的长度，T 我编写了 C++ 代码并测试了它的工作原理。

这个想法是比较S和T的第一个字符：

First count how many digits S and T have, then compare their first characters

if(S[0] < T[0])
    can remove any digits behind except for the first characters of S and T
    then check if you can remove S[0] or T[0] to make S<T
else
    check if you can remove S[0] or  T[0] to make S<T if can not, return 0;
于 2019-08-27T06:08:58.747 回答
0 
System.out.println(getcnt(s1, t1) + getcnt(t1, s1));

    public static int getcnt(String a, String b) {
    int ways = 0;
    for (int i = 0; i < a.length(); i++) {

        if (Character.isDigit(a.charAt(i))) {

            String s = a.substring(0, i) + a.substring(i + 1);

            if (s.compareTo(b) < 0 || b.compareTo(s) < 0)
                ways++;

        }
    }
    return ways;
}
于 2019-11-17T12:24:32.283 回答
0

这是具有O(n+m)时间复杂度的工作解决方案。只有第一个字符很重要，根据它的数量，我们可以决定如何处理它。

public static int numSmaller(String s, String t) {
    return numSmaller(s,t,1);
}
public static int numSmaller(String s, String t,int n) {
    if(n==0){
        if(s.compareTo(t) < 0){
            return 1;
        }else{
            return 0;
        }
    }
    int output = 0;
    if(n==1){
        char sc = s.charAt(0);
        char tc = t.charAt(0);
        int sCount = digitCount(s);
        int tCount = digitCount(t);
        if(sc < tc){
            if(Character.isDigit(sc)){// s = '123ab' and t = 'c23cd',
                output += ((sCount-1)+tCount);//we need to delete exactly one character
                output+=numSmaller(s.substring(1),t,0);
            }else{
                output += (sCount)+tCount;
            }

        }else{
            if(!Character.isDigit(sc) && !Character.isDigit(tc) ){
                return 0;
            }
            if(Character.isDigit(sc)){
                output +=numSmaller(s.substring(1),t,0);
            }
            if(Character.isDigit(tc)){
                output +=numSmaller(s,t.substring(1),0);
            }
        }
    }
    return output;

}
 private static int digitCount(String s){
    int count = 0;
    for(int i=0;i<s.length();i++){
        char c = s.charAt(i);
        if(Character.isDigit(c)){
            count++;
        }
    }
    return count;
}
 /**
    String s="a123ab";
    String t ="b423cd";
    System.out.println( numSmaller(s,t));
    
     * a23ab,b423cd
     * a13ab,b423cd
     * a12ab,b423cd
     * a123ab,b23cd
     * a123ab,b43cd
     * a123ab,b42cd
     *
     */
于 2020-12-03T21:50:34.090 回答
0

仅依赖于检查第一个字符的 O(n+m) 解决方案对此输入失败

s = "ab12c"
t = "ab24z"

只检查第一个字符仍然是一个很大的改进，但必须处理边缘情况

于 2021-11-18T05:17:52.710 回答