javastringrecursionindexoutofboundsexception

How to recursively check if a String starts and ends with another String in Java without equals()?


I need to write a method private static boolean textStartSeqEndSeq(String text, String sequence).

The method compares text and sequence, where sequence has to be at the start and at the end of text. So, it must be contained at least twice in text.

For example: text "ABCDEFG" and sequence "AB" are only partly true, so return false. text "AB123AB" and sequence "AB" would return true. This would normally be easy, but here are the restrictions:

I'm probably overthinking this because I have been stuck on this for a while now, but all I get is error after error. I just can't figure out what I'm doing wrong, also I am a beginner, so for you this might seem obvious and you can help me. Here is the code I've got so far:

    private static boolean textStartSeqEndSeq(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 textStartSeqEndSeq(text.substring(i + 1), sequence.substring(i + 1));

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

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

And here are the errors I'm getting, it stops processing before it reaches 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

Solution

  • Using indexes won't help you in this situation, since you're not allowed to pass them to a utility method or to iterate over the strings.

    What you could do is to make sure that the first character in the sequence string corresponds to the characters in the first and text.length() - sequence.length() position in text.

    If these 2 conditions are met, you could advance with a recursive call and pass a substring of both text and sequence without their first character. Basically, at each recursive step you're reducing the portions of strings to confront, until there is only 1 character left in sequence.

    private static boolean isStartAndEndSeq(String text, String sequence) {
        Objects.requireNonNull(text);
        Objects.requireNonNull(sequence);
    
        if (text.isEmpty() ||
                sequence.isEmpty() ||
                sequence.length() > text.length()){
            return false;
        }
    
        //make sure that the first character in sequence matches the first character in text
        return sequence.charAt(0) == text.charAt(0) &&
                //make sure that the first character in sequence matches the first character in the substring at the end of text
                sequence.charAt(0) == text.charAt(text.length() - sequence.length()) &&
                //if there is only 1 character left in sequence we're done, because that character is being confronted during the current call, otherwise we need to advance to the next subset of the two strings
                (sequence.length() == 1 || isStartAndEndSeq(text.substring(1), sequence.substring(1)));
    }
    

    Here is also a demo at OneCompiler with your expected output. In the demo, I've also added extra cases suggested in the comments. Thank you @user85421 and @k314159 for your comments.