java - (Java) 字母子串比较以错误结果结束

Question

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

问题

We define the following terms:

• Lexicographical Order, also known as alphabetic or dictionary order, orders characters as follows: A < B < ...< Y < Z < a < b ... < y < z

• A substring of a string is a contiguous block of characters in the string. For example, the substrings of abc are a, b, c, ab, bc, and abc.

Given a string, s, and an integer, k, complete the function so that it finds the lexicographically smallest and largest substrings of length 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

在 Debug模式下，我发现最小的子串直到第 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 和最小。