如何在Java中递归检查一个字符串是否以另一个字符串开头和结尾而不使用equals()？

Question

我需要写一个方法

private static boolean textStartSeqEndSeq(String text, String sequence)

。

该方法比较

text

和

sequence

，其中

sequence

必须位于

text

的开头和结尾。因此，它必须至少包含在

text

中两次。

例如： 文本“ABCDEFG”和序列“AB”仅部分为真，因此返回 false。 文本“AB123AB”和序列“AB”将返回 true。 这通常很容易，但有以下限制：

• 没有辅助方法，只有一个方法和主方法。
• 没有循环或数组，只有递归。
• 仅使用

  isEmpty()

  、

  length()

  、

  substring()

  和

  charAt()

  ，请勿使用

  equals()

  。

我可能想得太多了，因为我已经被困在这个问题上有一段时间了，但我得到的只是一个又一个的错误。我只是不知道我做错了什么，而且我是初学者，所以对你来说这可能看起来很明显，你可以帮助我。这是我到目前为止得到的代码：

    private static boolean isStartAndEndSeq(String text, String sequence) {
        // Base cases
        if (text.isEmpty() || sequence.isEmpty() || sequence.length() > text.length()) {
            return false;
        }
        if (sequence.length() * 2 > text.length()) {
            return false; // Not enough room for sequence at both start and end
        }

        int i = 0, j = 0;
        boolean start = false, end = false;
        String case1 = text.substring(0, sequence.length() - 1);
        String case2 = text.substring(text.length() - sequence.length());

        // Check if `text` starts with `sequence` using recursion
        if (!start) {
            if (case1.charAt(i) != sequence.charAt(i)) {
                return false;
            }
            return isStartAndEndSeq(text.substring(i + 1), sequence.substring(i + 1));

        }
        if (!end) {
            if (text.charAt(j) != sequence.charAt(j)) {
                return false;
            }
            return isStartAndEndSeq(text.substring( j + 1), sequence.substring(j + 1));
        }
        return start && end;
    }

    public static void main(String[] args) {
        System.out.println(isStartAndEndSeq("AB123AB", "AB"));// Expected: true
        System.out.println(isStartAndEndSeq("ABBA", "AB"));// Expected: false
        System.out.println(isStartAndEndSeq("ottootto", "otto"));// Expected: true
        System.out.println(isStartAndEndSeq("Golden Yacht", "acht"));// Expected: false
        System.out.println(isStartAndEndSeq("blue whales are blue", "blue"));// Expected: true
        System.out.println(isStartAndEndSeq("", "A"));// Expected: false
        System.out.println(isStartAndEndSeq("A", ""));// Expected: false
        System.out.println(isStartAndEndSeq("A B C D", " "));// Expected: false
    }
}

这是我遇到的错误，它在到达 if (!end){} 之前停止处理：

C:\Users\Administrator\.jdks\corretto-21.0.3-3\bin\java.exe "-javaagent:C:\Program Files\JetBrainsNew\IntelliJ IDEA Community Edition 2024.2.3\lib\idea_rt.jar=56733:C:\Program Files\JetBrainsNew\IntelliJ IDEA Community Edition 2024.2.3\bin" -Dfile.encoding=UTF-8 -Dsun.stdout.encoding=UTF-8 -Dsun.stderr.encoding=UTF-8 -classpath C:\Users\Administrator\IdeaProjects\ProgrammersProgram\out\production\ProgrammersProgram Temp
Exception in thread "main" java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
    at java.base/jdk.internal.util.Preconditions$1.apply(Preconditions.java:55)
    at java.base/jdk.internal.util.Preconditions$1.apply(Preconditions.java:52)
    at java.base/jdk.internal.util.Preconditions$4.apply(Preconditions.java:213)
    at java.base/jdk.internal.util.Preconditions$4.apply(Preconditions.java:210)
    at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:98)
    at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:106)
    at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:302)
    at java.base/java.lang.String.checkIndex(String.java:4832)
    at java.base/java.lang.StringLatin1.charAt(StringLatin1.java:46)
    at java.base/java.lang.String.charAt(String.java:1555)
    at Temp.isStartAndEndSeq(Temp.java:29)
    at Temp.isStartAndEndSeq(Temp.java:32)
    at Temp.main(Temp.java:45)

Process finished with exit code 1

Answer 1

在这种情况下使用索引不会有帮助，因为不允许将它们传递给实用方法或迭代字符串。

您可以做的是确保

sequence

字符串中的第一个字符对应于

text.length() - sequence.length()

中第一个和

text

位置的字符。同时，

sequence

中的最后一个字符对应于

sequence.lentgh() - 1

中的最后一个和

text

位置。

如果满足这 4 个条件，您可以通过递归调用前进并传递

text

和

sequence

的子字符串，而不需要它们各自的第一个和最后一个字符。基本上，在每个递归步骤中，您都会减少要面对的字符串部分，直到

sequence

中只剩下 2 个字符。

private static boolean isStartAndEndSeq(String text, String sequence) {
    Objects.requireNonNull(text);
    Objects.requireNonNull(sequence);

    if (text.isEmpty() ||
            sequence.isEmpty() ||
            sequence.length() > text.length() ||
            sequence.length() * 2 > text.length()) {
        return false;
    }

    return sequence.charAt(0) == text.charAt(0) &&  //make sure that the first character in sequence matches the first character in text
            sequence.charAt(0) == text.charAt(text.length() - sequence.length()) && //make sure that the first character in sequence matches the first character in the substring at the end of text
            sequence.charAt(sequence.length() - 1) == text.charAt(sequence.length() - 1) && //make sure that the last character in sequence matches the last character in the substring at the beginning of text
            sequence.charAt(sequence.length() - 1) == text.charAt(text.length() - 1) && //make sure that the last character in sequence matches the last character in text
            (sequence.length() == 2 || isStartAndEndSeq(text.substring(1, text.length() - 1), sequence.substring(1, sequence.length() - 1))); //if there are 2 characters left in sequence we're done, because those 2 characters are being confronted during the current call, otherwise we need to advance to the next subset of the two strings
}

这里还有 OneCompiler 的演示，其中包含您的预期输出。