2ms super easy to understand java solution with explanation


  • 1
    1. First we need to make sure if "s" is a valid input for generating palindromes. countPalindrome() will return a StringBuilder containing half of letters in "s" if "s" is valid and s.length is an even number; or return s.length - 1 letters if s.length is an odd number; If "s" is not a valid input, a null will be returned;
      At the same time "charCenter " will be set to the center letter if a valid input string's length is odd, or '0' if it is not valid;
      eg. s = "aabbcc" return "abc" charCenter = '0', s = "123123d" return "123" charCenter = 'd'
      s = "abcv" return null;

    2. After getting those half valid letters and a charCenter, we can use backtrack method to generate all permutations of those letters, and get the answer by adding their reversed strings to their tails;

          public class Solution {
            static int Len;
        	static char charCenter; 
        	static final int R = 128;//128 is enought for this problem
            public static List<String> generatePalindromes(String s) {
                List<String> list = new ArrayList<>();
                if(s == null || s.length() == 0)
                    return list;
        	        StringBuilder sb1 = countPalindrome(s);//get those half valid letters or null if s is not valid input
        		if(sb1 == null)
        			return list;
    		s = sb1.toString();//replace the string with what we got. 
            char[] charArr = s.toCharArray();
            Len = charArr.length;
            boolean[] visited = new boolean[Len];//used to mark what letters are visited
            Arrays.sort(charArr);
            StringBuilder sb2 = new StringBuilder();
            backtrack(charArr,list,visited,sb2);
            return list;
        }
    	public static StringBuilder countPalindrome(String s)
    	{
    
    		int[] count = new int[R];
    		char[] charArr = s.toCharArray();
    		StringBuilder sb = new StringBuilder();
    		Arrays.sort(charArr);//sort it for the convenience of latter use, does not really matter
    		int single = 0;
    		for(int i = 0 ; i < charArr.length; i++)
    		{
    			int index = charArr[i];
    			count[index] += 1;//use the letter's ASCII as index of count
    			single++;
    			if(count[index] == 2)
    			{
    				count[index] = 0;
    				single -= 2;//single minus 2 not 1, because you counted every letter you are dealing with
    				sb.append(charArr[i]);//append the letter in sb when we got two of them
    			}
    		}
    		if(single > 1) return null;//there should be only 0 or 1 center for a valid string
    		else if(single == 1)//find the center if there is one.
    		{
    			for(int i = 0; i < R; i++)
    			{
    				if(count[i] == 1)
    				{
    					charCenter = (char)(i);
    				}
    			}
    		}
    		else 
    			charCenter = '0';//set charCenter to '0' if it does not exist a center.(Actually there will be a problem if the real center is '0', I don't care LOL)
    		return sb;
    		
    	}
        public static void  backtrack(char[] charArr, List<String> list, boolean[] visited, StringBuilder sb)
        {
            if(sb.length() == Len )
            {
                list.add(sb.toString()+(charCenter == '0'?"":charCenter)+sb.reverse().toString());
                sb.reverse();//remeber to reverse sb back for further usage.
            }
            for(int i = 0 ; i < Len ; i++)
            {
                if(visited[i]||(i>0&&!visited[i-1]&&charArr[i] == charArr[i-1]))//this prevent you from dealing with the same letters which you have already dealt with. Key point is !visited[i-1].
                    continue;
                visited[i] = true;
                sb.append(charArr[i]);
                backtrack(charArr,list,visited,sb);// What a classic version of backtrack method!
                visited[i] = false;//remember to "false" back
                sb.deleteCharAt(sb.length()-1);
            }
        }
    }

Log in to reply
 

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