CODEWITHSUNDEEP
javalistarraylistpalindrome
user2918863
user2918863

Reputation: 79

Tracking palindromes from a list of strings in Java

I have been spending hours trying to work through the logic of finding a palindrome within this context. So we are given an arraylist of strings that are single words and we need to find the biggest palindromes from the list of words. As an example ["mr", "owl", "ate", "my", "metal", "worm", "racecar", "mad", "am"] would construct an araylist with the following result ["mrowlatemymetalworm", "racecar", "madam"]. So far I have been playing around with the iterations but can't seem to get the correct logic of how to iterate from both ends, especially when it comes to switching inner strings indexes from the other end... Here is what I have so far. 

    List<String> list = Arrays.asList("mr", "owl", "ate", "my", "metal", "worm", "racecar", "mad", "am");       
    List<String> palindromeList = new ArrayList<String>(); 
    int i = 0; 
    int j = list.get(i).length(); 
    int l = list.size()-1; 
    int s = list.get(l).length() -1; 
    while (i<j){

        while (j<list.get(i).length()){

            if (s == 0){

                //need to reinitialize s for previous index of back end of list for possible palindrome  
            }

            if (list.get(l).charAt(s) == list.get(i).charAt(j)){

                l--; 

            }

            else if (list.get(l).charAt(s) != list.get(i).charAt(j)){

                j++; 
                s--; 
            }
        }
    }

    //once outer loop breaks the result should be added to palindromeList

Upvotes: 0

Views: 2724

Answers (3)

Edward Doolittle
Edward Doolittle

Reputation: 4100

It's important to know whether words can be repeated or not. If they can, then you could have "racecarracecar", "racecarracecarracecar", etc., so I assume they can't. In that case we can proceed as follows. Walk through the list of words, starting with "mr". If the palindrome begins with "mr" it must end with "m". Does "am" work? No. Try other possibilities; "worm" works. Then an "o" must follow "mr". The next word at the beginning must be "owl". That means the next word at the end must end with "l" so must be "metal".

Etc., until you 1) run out of words, 2) have a palindrome, or 3) have a palindrome like "doggod" where word boundaries are exactly in the middle, in which case you can (recursively) search for more palindromes with the remaining words and put anything you get in the middle, like "dogracecargod" or "dogmadamgod" or "dogmrowlatemymetalwormgod".

Upvotes: 0

Marek Adamek
Marek Adamek

Reputation: 520

You can verify if string is a palindrome by comparaing if it's equal with itself reversed (that's exact definition):

public static boolean isPalindrome(String value) {
    if (value == null || value.isEmpty())
        return false;

    return new StringBuilder(value).reverse().toString().equals(value);
}

I'm not sure if I understood the logic you want to apply, but based on the input and output you gave I came up with something like this:

List<String> list = Arrays.asList("mr", "owl", "ate", "my", "metal", "worm", "racecar", "mad", "am");
List<String> palindromeList = new ArrayList<String>();

for (int i = 0; i < list.size(); ++i) {
    String longestPalindrome = null;
    String candidate = "";
    for (int j = i; j < list.size(); ++j) {
        candidate += list.get(j);
        if (isPalindrome(candidate))
            longestPalindrome = candidate;
    }

    if (longestPalindrome != null)
        palindromeList.add(longestPalindrome);
}

Upvotes: 1

Andy T
Andy T

Reputation: 136

To detect if a string is a palindrome, I split the string in half, reverse the string and see if both sides equal each other.

There are 2 scenarios:

Word has even number of characters:

If the string is of odd length, we split the string into 2 substrings excluding the middle character: Ex: ABCBA would be broken into AB and BA. We then reverse the string and compare to see if they equal each other.

Word has odd number of characters:

If the string is of even length, we just split the string into 2 equal size substrings and reverse one of them then compare to see if they are the same string. Ex: Hannah would be Han and nah.

List<String> list = Arrays.asList("mr", "owl", "ate", "my", "metal", "worm", "racecar", "mad", "am");
List<String> palindromeList = new ArrayList<String>(); 

//Detects if a string is a palindrome.

for (int i = 0; i < list.size(); i ++) {List<String> palindromeList = new ArrayList<String>();
    int wordLength = list.get(i);

    String leftSide = "";
    String rightSide ="";

    if (wordLength%2 == 1) { //If word has odd number of characters.
        leftSide = list.get(i).subString(0,wordLength/2);
        rightSide = list.get(i).subString((wordLength/2) + 1, wordLength);

    } else { //If word has even number of characters.
        leftSide = list.get(i).subString(0,(wordLength/2));
        rightSide = list.get(i).subString((wordLength/2), wordLength);
    }
    String reversedLeftSide = new StringBuilder(leftSide).reverse().toString();
    if (reversedLeftSide.equals(rightSide)) {
        palindromeList.add(list.get(i));
    }
}

String longestPalindrome = "";

//Searches for longest palindrome in the list of palindromes.

for (int i = 0; i < palindromeList.size(); i++) {
    if (palindromeList.get(i).length() > longestPalindrome.length()) {
        longestPalindrome = palindromeList.get(i);
    }
}

System.out.println(longestPalindrome); //This should give you longest palindrome.

Keep in mind there are probably a dozen ways to solve this problem and I've just proposed one solution. This code might also contain 1 or 2 minor bugs as it has not been tested.

Upvotes: 0

Related Questions