My O(n) Java code generates shorter palindromes


  • 0
    N

    This code generates shorter palindromes, for example - for "aabba", my code generates "abbabba", but the expected output should be "abbaabba".

    I dont know why? Can someone point out what is wrong with my code?

    public String shortestPalindrome(String s) {
            if(s.length() == 0){
                return s;
            }
            List<Character> list = new ArrayList<>();
            for(char x: s.toCharArray()){
                list.add(x);
            }
            int p = 0, q = s.length()-1;
            while(p<q){
                if(list.get(p).equals(list.get(q))){
                    p++; q--;
                }else{
                    list.add(p, list.get(q));
                    q++;
                }
            }
            StringBuilder str = new StringBuilder();
            for(char x : list){
                str.append(x);
            }
            return str.toString();
        }

  • 0
    L

    Because you are only allowed to convert it to a palindrome by adding characters in front of it. You are not allowed to insert.

    Hope it helps : )


  • 0
    B

    I think the problem should be in the while loop, in else should be p++ instead of q++.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.