Solution to a Palindrome Searcher exercise

exercisePalindrome.md

Palindrome searcher

What the hell is a palindrome?

Exercise

Create a function named searchPalindrome() following your current language's style guide. It should take a string, search for palindromes that is at least 3 characters long and return a list with the found palindromes.

Examples

input	output
"dog goat dad duck doodle never"	["og go", "g g", " dad ", "dad", "d d", "dood", "eve"]
"apple"	[]
"racecar"	["racecar", "aceca", "cec"]
""	[]

PalindromeSearcher.java

import java.util.ArrayList;
import java.util.List;

public class PalindromeSearcher {

    public static void main(String[] args) {
        List<String> result = searchPalindrome("dog goat dad duck doodle never");
        // List<String> result = searchPalindrome("racecar");

        // Print output one by one
        for (String element : result) {
            System.out.println("'".concat(element).concat("'"));
        }
    }

    /**
     * Search for palindromes longer than 3 characters in input string.
     * 
     * We do this by iterating over the string letter by letter. We search for two types of palindromes: symmetrical (dood) and
     * asymmetrical (dod).
     * 
     * Symmetrical palindromes:
     * At each letter N we check if letter N+1 is the same. If yes, we continue checking letters N-1 and N+2, then letters
     * (N-2, N+3), then letters (N-3, N+4) and so on until we reach the beginning or end of the string.
     * 
     * If ever the two letters are not the same, we stop searching and move on to the next position.
     * 
     * 
     * Asymmetrical palindromes:
     * At each letter N we check letters N+1 and N-1. If these are the same, we save the string as a palindrome 
     * and continue searching with (N+2, N-2), (N+3, N-3) until we reach the beginning or end of the string. 
     * 
     * If N-1 is not the same as N+1 we stop searching immediately and move to the next position in the string.
     * 
     * @param input String with possible palindromes in it
     * @return List of palindromes longer than 3 characters.
     */
    static List<String> searchPalindrome(String input) {
        List<String> outputPalindromes = new ArrayList<>();

        //Iterate over input, starting at position 1
        for (int i = 1; i < input.length() - 2; i++) {
            String maybePalindrome;

            // Symmetrical palindrome (e.g. 'oggo')
            if (input.charAt(i) == input.charAt(i + 1)) {

                maybePalindrome = input.substring(i, i + 2);

                //Iterate over all pairs of letters expanding outwards (towards the ends of the string).
                int j = 0;
                while (j < input.length() && (i - j) > 0) {
                    j++;
                   
                    if (input.charAt(i - j) == input.charAt(i + 1 + j)) {
                        //If the two letters are the same, expand the palindrome and save it
                        String newPalindromeLetter = Character.toString(input.charAt(i - j));
                        maybePalindrome = newPalindromeLetter.concat(maybePalindrome).concat(newPalindromeLetter);

                    } else {
                        // Stop searching for palindrome from this position
                        break;
                    }

                    // Add to output list if palindrome is longer than 3 characters
                    if (maybePalindrome.length() >= 3) {
                        outputPalindromes.add(maybePalindrome);
                    }
                }

            }

            // Search for asymmetrical palindromes (e.g. 'racecar')
            else {
                maybePalindrome = Character.toString(input.charAt(i));

                //Iterate over all pairs of letters expanding outwards (towards the ends of the string).
                int j = 0;
                while (i - j > 0 && i + j < input.length() - 1) {
                    j++;

                    if (input.charAt(i - j) == input.charAt(i + j)) {
                        //If the two letters are the same, expand the palindrome and save it
                        String newPalindromeLetter = Character.toString(input.charAt(i - j));
                        maybePalindrome = newPalindromeLetter.concat(maybePalindrome).concat(newPalindromeLetter);

                    } else {
                        // Stop searching for palindrome from this position
                        break;
                    }

                    if (maybePalindrome.length() >= 3) {
                        // Add to output list if palindrome is longer than 3 characters
                        outputPalindromes.add(maybePalindrome);
                    }
                }
            }
        }

        return outputPalindromes;
    }
}