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

Question

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:

• No helper methods, only one method and the main method.
• No loops or arrays, only recursion.
• Only use isEmpty(), length(), substring() and charAt().

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

Answer 1

Here is a different version...

boolean isStartAndEndSeq( String text, String sequence ) {
   if( text == null || text.length() == 0 || sequence.length() == 0 )  return false;      
   if( sequence.length() == 0 ) return true;          
   if( text.charAt( 0 ) != sequence.charAt( 0 ) ||
           text.charAt( text.length() - 1 ) != sequence.charAt( sequence.length() - 1 ) ) return false;      
   return isStartAndEndSeq( text.substring( 1, text.length() ), sequence.substring( 1, sequence.length() ) );
}

Answer 2

Here is one approach.

record TestData(String getText, String getSequence) {
}

public static void main(String[] args) {
    List<TestData> testCases = List.of(
            new TestData(null, null),
            new TestData("oooo", "o"),
            new TestData("fooxxxxxfoo", "foo"),
            new TestData("fooxxxxxfo", "fo"),
            new TestData("fooxxxxxf", "f"),
            new TestData("fooxxxxxf", "f"),
            new TestData("fooxxxxxfo", "fo"),
            new TestData("foxxxxxf", ""),
            new TestData("", "f"),
            new TestData("", ""),
            new TestData("aboxxxxxab", "ab"),
            new TestData("abab", "ab"),
            new TestData("ffff", "fff"),
            new TestData("ffff", "ffff"),
            new TestData("aba", "ab"));

    for (TestData td : testCases) {
        System.out.printf("%-13s %-4s - %b%n", td.getText(), td.getSequence(), 
                isStartAndEndSeq(td.getText(), td.getSequence()));
    }
}

Prints

null          null - false
oooo          o    - true
fooxxxxxfoo   foo  - true
fooxxxxxfo    fo   - true
fooxxxxxf     f    - true
fooxxxxxf     f    - true
fooxxxxxfo    fo   - true
foxxxxxf           - false  // empty sequence
              f    - false  // empty text
                   - false  // empty both
aboxxxxxab    ab   - true
abab          ab   - true
ffff          fff  - true
ffff          ffff - true
aba           ab   - false

The Process

• first, check for illegal parameters and if found, return false.
• Then it's just a matter of checking the first character of the expected sequence against its expected locations in the text string.
• if all is well, advance the to the next sequence character and text characters by the use of substring.
• if the sequence string is empty, return true as all characters have been located in text.
• otherwise, and do a recursive call with the modified text and sequence strings.

private private static boolean isStartAndEndSeq(String text, String sequence) {
        // fail fast cases
        if (text == null || sequence == null || text.isEmpty()
                || sequence.isEmpty() || text.length() < sequence.length()) {
            return false;
        }

        char seqCharUnderTest = sequence.charAt(0);
        char endingTextCharUnderTest = text
                .charAt(text.length() - sequence.length());

        if ( endingTextCharUnderTest != seqCharUnderTest 
                || text.charAt(0) != seqCharUnderTest) {
            return false;
        }
        sequence = sequence.substring(1);
        if (sequence.isEmpty()) {
            return true;
        }
        return isStartAndEndSeq(text.substring(1), sequence);

    }
}

Notes

• No where did you specify how to hand null strings. I chose to return false.
• Nor did you specify how to handle "text = "xxx" and sequence = "xx" or "xxx". So I opted to return true since the text does indeed start and end with those sequences, even though some characters are "shared."

Answer 3

Reading stack traces is an important skill. Consider yours:

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)

Entries are ordered from most recent to least, and you should be able to see that the last bunch are all inside the Java standard library. Those you can mostly ignore, except for the last, which tells you what standard library method your code invoked to provoke the exception. And the following entry tells you exactly on which line of which source file that invocation occurs. In this case, the exception message, at the top, fleshes out the picture pretty well:

At line 29 of your Temp.java, at recursion depth 2 in Temp.isStartAndEndSeq(), that method invokes chartAt(0) on a String that has length 0. It looks like that is going to be one of the two charAt() invocations on this line:

            if (case1.charAt(i) != sequence.charAt(i)) {

You've previously verified that sequence is non-empty, so it must be case1 that is. And that's possible because initializing it as

        String case1 = text.substring(0, sequence.length() - 1);

makes it shorter than sequence, which itself could be as short as length 1.

I don't really follow what you're trying to do with that. Among other things, do note that each invocation of your method gets its own local variables, including i and j, and you do not modify those after initializing them, so it would be clearer, and equivalent, to replace them with constants. But it also appears that you are making case1 an initial substring of sequence, and then checking whether it is, in fact, an initial substring. I can tell you without computing anything that yes, it is.

Suggested approach

Recursion solves a problem at least partially in terms of the solution to a smaller version of the same problem. Since you cannot have any helper methods, the problem to solve using such an approach is exactly the problem given (not a sub-problem). That is, does a given string both start and end with a specified substring. A smaller version of the same problem would mean a smaller target string, a smaller test sequence, or both.

In considering how to structure such a solution recursively, it might help to think about how you might approach a simpler yet similar problem: the one where you have to check only for a subsequence match at the beginning of the target string. This is more straightforward, for you can compare the first characters, and on a match, compare the two tails after the first character. From there, adding a test for a match at the end, as well, is not that big a stretch.

Supposing that the head and tail sequences are not allowed to overlap (which your code seems already to assume), I would not separate testing the head substring and tail substring into separate cases. The basic operation would instead be

1. Handle base cases, that

   • the test sequence is length 0 (result true (!))
   • the target string is shorter than twice the test sequence length (result false)

2. Check that the first character of the test sequence matches both at the beginning of the target string and at the appropriate position near the end of the target string. (Note: not matching the two string ends, unless the test sequence is only one character.)

   • If either position does not match then return false
   • If both match then recurse to test the next position of the sequence. The arguments to the recursive call will be the target string with the two just-matched characters removed and the tail of the test sequence after the first (just matched) character.

Answer 4

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.