Monday, June 6, 2016

Leetcode: 336. Palindrome Pairs

Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.
Example 1:
Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]
Example 2:
Given words = ["abcd", "dcba", "lls", "s", "sssll"]
Return [[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]
Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Code (Java):
public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = new ArrayList<>();
        
        if (words == null || words.length == 0) {
            return result;
        }
        
        // step1: put the reverse order of the words into a map
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            String rWord = reverse(words[i]);
            map.put(rWord, i);
        }
        
        // step 2 & 3: check the prefix of each word. 
        // It can form a palindrome iff prefix in the map AND 
        // rest substring is a palindrome. 
        // e.g. abll, if the prefix is ab, and the map contains a "ab", then
        // we can form a palindrome which is abllba
        
        // check the postfix of each word. 
        // The word can form a palindrome iff postfix is in the map AND
        // the rest of prefix is a palindrome
        // e.g. llab, where the postfix is ab, if the map cotnains a "ab", then
        // we can form a palindrome of ballab
        for (int j = 0; j < words.length; j++) {
            String word = words[j];
            
            // get prefix of each word
            for (int i = 0; i <= word.length(); i++) {
                String prefix = word.substring(0, i);
                String rest = word.substring(i);
                if (map.containsKey(prefix) && isPalindrome(rest) && 
                    map.get(prefix) != j) {
                    List<Integer> curr = new ArrayList<>();
                    curr.add(j);
                    curr.add(map.get(prefix));
                    result.add(curr);
                }
            }
            
            // get postfix of each word
            for (int i = word.length(); i > 0; i--) {
                String postfix = word.substring(i);
                String rest = word.substring(0, i);
                if (map.containsKey(postfix) && isPalindrome(rest) && 
                    map.get(postfix) != j) {
                    List<Integer> curr = new ArrayList<>();
                    curr.add(map.get(postfix));
                    curr.add(j);
                    result.add(curr);
                }
            }
        }
        
        return result;
    }
    
    private String reverse(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        char[] array = s.toCharArray();
        int start = 0;
        int end = array.length - 1;
        
        while (start < end) {
            swap(start, end, array);
            start++;
            end--;
        }
        
        return new String(array);
    }
    
    private void swap(int start, int end, char[] array) {
        char temp = array[start];
        array[start] = array[end];
        array[end] = temp;
    }
    
    private boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        
        int start = 0;
        int end = s.length() - 1;
        
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        
        return true;
    }
}

Analysis:
Assume the number of words is n, and the average length of a word is m. The average time complexity is O(m^2 * n). 
Space complexity: O(n) since we use a map to store all the words

7 comments:

  1. This comment has been removed by a blog administrator.

    ReplyDelete
  2. Valuable blog,Informative content...thanks for sharing, Waiting for the next update…

    TOEFL Training in Chennai
    TOEFL Coaching Centres in Chennai

    ReplyDelete
  3. Valuable blog,Informative content...thanks for sharing, Waiting for the next update…

    French Courses in Chennai
    French Institute in Chennai

    ReplyDelete
  4. You've made some valid statements there. I looked on the web for extra data about the issue and discovered a great many people will oblige your perspectives on this site.best interiors

    ReplyDelete