107ms AC Java Solution-Time Complexity is O(N*K)--N is size of words, K is avg length of a word


  • 2
    Q
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> res =new ArrayList<>();
        if(words == null|| words.length <2)
        	return res;
        
        Map<String,Integer> word_idx = new HashMap<>();
        
        for( int i = 0 ; i< words.length ; i++)
        	word_idx.put(words[i], i);
        
    	for (int i = 0; i < words.length; i++) {
    		String aWord = words[i];
    		if (aWord.length() > 0) {
    			if (!isPalindrome(aWord, 0, aWord.length() - 1)) {
    
    				String comple = reverseLetters(aWord, 0, aWord.length() - 1);
    
    				if (word_idx.containsKey(comple)) {
    					List<Integer> aCombo = new ArrayList<>();
    					aCombo.add(i);
    					aCombo.add(word_idx.get(comple));
    					res.add(aCombo);
    				}
    
    			} else {
    				String comple = "";
    				if (word_idx.containsKey(comple)) {
    					List<Integer> aCombo = new ArrayList<>();
    					aCombo.add(i);
    					aCombo.add(word_idx.get(comple));
    					res.add(new ArrayList<Integer>(aCombo));
    					aCombo.set(0, aCombo.set( 1,aCombo.get(0) ) );
    					res.add(aCombo);
    				}
    			}
    
    			for (int j = 0; j < aWord.length(); j++) {
    
    				if (j + 1 < aWord.length() && isPalindrome(aWord, 0, j)) {
    					String comple = reverseLetters(aWord, j + 1,
    							aWord.length() - 1);
    
    					if (word_idx.containsKey(comple)) {
    						List<Integer> aCombo = new ArrayList<>();
    						aCombo.add(word_idx.get(comple));
    						aCombo.add(i);
    						res.add(aCombo);
    					}
    
    				}
    
    				if (0 < j && j < aWord.length()
    						&& isPalindrome(aWord, j, aWord.length() - 1)) {
    
    					String comple = reverseLetters(aWord, 0, j - 1);
    
    					if (word_idx.containsKey(comple)) {
    						List<Integer> aCombo = new ArrayList<>();
    						aCombo.add(i);
    						aCombo.add(word_idx.get(comple));
    						res.add(aCombo);
    					}
    
    				}
    			}
    		}
        }
        
        return res;
    }
    
    private boolean isPalindrome(String aWord, int start, int end){
    	
    	if(end == start ) return true;
    	
    	int mid = (end+start+1)/2;
    	
    	for(int i = start ; i < mid ; i ++){
    		if(aWord.charAt(i) != aWord.charAt(end+start-i))
    			return false;
    	}
    	
    	return true;
    }
    
    private String reverseLetters(String s , int start, int end){
    	if(end == start) return String.valueOf(s.charAt(end));
    	StringBuffer sb = new StringBuffer();
    	
    	for( int i = end ; i>= start ; i--)
    		sb.append(s.charAt(i));
    	
    	return sb.toString();
    }

  • 0
    W

    It is O(n*k^2)


  • 0
    Z

    you are right, it is O(NKK)


Log in to reply
 

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