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

4 comments:

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

    ReplyDelete
  2. New Diet Taps into Revolutionary Plan to Help Dieters LOSE 20 Pounds within Only 21 Days!

    ReplyDelete
  3. Awesome Article Written By the Author.
    Amazing News Shared.
    Do you know what is anti adware? and how to remove cryptominers ransomware malware? If no then read more on the article.
    Read more closely on the topic of how to remove music finder from your system.
    Also check the best way to remove shortcut virus easily.

    ReplyDelete