（Java）字母子串比较最终得到错误的结果

Question

在这些 HackerRank Java 挑战之一中，有一个问题定义为：

问题

我们定义以下术语：

• 词典顺序，也称为字母顺序或字典顺序，字符顺序如下：A < B < ...< Y < Z < a < b ... < y < z

• 字符串的子字符串是字符串中连续的字符块。例如，abc的子串为a、b、c、ab、bc、abc。

给定一个字符串 s 和一个整数 k，完成 函数，以便它找到按字典顺序排列的 smallest 和 最大长度为k的子串。

这是我的（不完全有效）解决方案：

我的代码

import java.util.*;

public class stringCompare {

    public static String getSmallestAndLargest(String s, int k) {
        String smallest, largest, temp;

        /* Initially, define the smallest and largest substrings as the first k chars */
        smallest = s.substring(0, k);
        largest = s.substring(0, k);

        for (int i = 0; i <= s.length() - k; i++) {
            temp = s.substring(i, i + k);
            for (int j = 0; j < k; j++) {

                /* Check if the first char of the next substring is greater than the largest ones' */
                if (temp.charAt(j) > largest.charAt(j)) {
                    largest = s.substring(i, i + k);
                    break;      
                }

                /* Check if the first char of the next substring is less than the smallest ones' */
                else if (temp.charAt(j) < smallest.charAt(j)) {
                    smallest = s.substring(i, i + k);
                    break;
                } 

                /* Check if the first char of the next substring is either equal to smallest or largest substrings' */
                else if (temp.charAt(j) == smallest.charAt(j)
                        || temp.charAt(j) == largest.charAt(j)) {
                    // If so, move to the next char till it becomes different
                } 

                /* If the first of char of the next substring is neither of these (between smallest and largest ones')
                    skip that substring */ 
                else {
                    break;
                }
            }
        }

        return smallest + "\n" + largest;
    }

    public static void main(String[] args) {
        String s;
        int k;
        try (Scanner scan = new Scanner(System.in)) {
            s = scan.next();
            k = scan.nextInt();
        }

        System.out.println(getSmallestAndLargest(s, k));
    }
}

根据 HackerRank，此代码在 6 种情况中有 2 种失败。其一如下：

ASDFHDSFHsdlfhsdlfLDFHSDLFHsdlfhsdlhkfsdlfLHDFLSDKFHsdfhsdlkfhsdlfhsLFDLSFHSDLFHsdkfhsdkfhsdkfhsdfhsdfjeaDFHSDLFHDFlajfsdlfhsdlfhDSLFHSDLFHdlfhs
30

预期输出是：

ASDFHDSFHsdlfhsdlfLDFHSDLFHsdl
sdlkfhsdlfhsLFDLSFHSDLFHsdkfhs

但是我的变成：

DFHSDLFHDFlajfsdlfhsdlfhDSLFHS
sdlkfhsdlfhsLFDLSFHSDLFHsdkfhs

在调试模式下，我发现最小的子串直到第 67 次迭代 (i) 为止都是正确的。我不知道为什么它在那一步变成了错误的，但它确实如此。

有人可以帮我吗？

谢谢！

Answer 1

问题是您正在尝试在单个循环中比较最大和最小。更具体地说，这一行是有问题的：

else if (temp.charAt(j) == smallest.charAt(j)
      || temp.charAt(j) == largest.charAt(j)) {
    // If so, move to the next char till it becomes different
}

您可能希望在

j

上继续循环以检测最小子字符串，但在

j

上跳出循环以检测最大子字符串。这就是为什么这两项检查应该彼此独立进行。

需要考虑的一些小要点：

• 你不需要写

  largest = s.substring(i, i + k)

  ，因为它和

  largest = temp

  一样；

  smallest

  也是如此。
• 您根本不需要嵌套循环

  compareTo

  为您执行字典顺序比较。

本质上，你的程序可以简化为：

largest = smallest = s.substring(0, k);
for (int i = 1 ; i <= s.length() - k; i++) {
    temp = s.substring(i, i + k);
    if (temp.compareTo(largest) > 0) {
        largestt = temp;
    } else if (temp.compareTo(smallest) < 0) {
        smalles = temp;
    }
}

请注意，循环可以从

i = 1

开始，因为您使用

s.substring(0, k)

来初始化

largest

和

smallest

。

Answer 2

您无法同时将某个子字符串与迄今为止最小的子字符串和迄今为止最大的子字符串进行比较。尤其是条件

temp.charAt(j) == smallest.charAt(j)
                    || temp.charAt(j) == largest.charAt(j)

有问题。举个例子吧

smallest   ad
largest    bx
temp       bc

在此示例中，您的代码将得出 bc 小于 ad 的结论

Answer 3

我提出了一个简单的优化：快速浏览第一个字符。

largest = smallest = s.substring(0, k);
for (int i = 1; i <= s.length() - k; i++) {
    if (s.charAt(i) > largest.charAt(0) ){
      largest = s.substring(i, i + k);
      continue;
    }
    if (s.charAt(i) < smallest.charAt(0) ){
      smallest = s.substring(i, i + k);
      continue;
    }

    if (s.charAt(i) == largest.charAt(0) ){
        String temp = s.substring(i, i + k);
        if( temp.compareTo(largest) > 0) {
            largest = temp;
            continue;
        }
    }
    if (s.charAt(i) == smallest.charAt(0) ){
        String temp = s.substring(i, i + k);
        if( temp.compareTo(smallest) < 0) {
            smallest = temp;
        }
    }
}

例如，比较次数从 222 下降到 14。

Answer 4

  public static String getSmallestAndLargest(String s, int k) {
     if (k == s.length()) {
        return s + "\n" + s;
    }
    String smallest = "z";
    String largest = "a";
    for (int i = 0; i <= s.length() - k; i++) {
if (s.charAt(i) > largest.charAt(0) ){
  largest = s.substring(i, i + k);
  continue;
}
if (s.charAt(i) < smallest.charAt(0) ){
  smallest = s.substring(i, i + k);
  continue;
}

if (s.charAt(i) == largest.charAt(0) ){
    String temp = s.substring(i, i + k);
    if( temp.compareTo(largest) > 0) {
        largest = temp;
        continue;
    }
}
if (s.charAt(i) == smallest.charAt(0) ){
    String temp = s.substring(i, i + k);
    if( temp.compareTo(smallest) < 0) {
        smallest = temp;
    }
}
    }
    
    
    // Complete the function
    // 'smallest' must be the lexicographically smallest substring of length 'k'
    // 'largest' must be the lexicographically largest substring of length 'k'
    
    return smallest + "\n" + largest;
}