Concise Python Solution


  • 3
    S
    class Solution(object):
        def palindromePairs(self, words):
            """
            :type words: List[str]
            :rtype: List[List[int]]
            """
            res = []
            dic = {}
            for i in range(len(words)):
                dic[words[i]] = i
            for word in words:
                word_rev = word[::-1]
                if word_rev in dic and dic[word_rev] != dic[word]:
                    res.append([dic[word_rev], dic[word]])
                for i in range(len(word)):
                    temp1 = word[:i][::-1]
                    temp2 = word_rev[:i]
                    if temp1 in dic and isPal(word[i:]):
                        res.append([dic[word], dic[temp1]])
                    if temp2 in dic and isPal(word_rev[i:]):
                        res.append([ dic[temp2], dic[word]])
            return res
    def isPal(word):
        left = 0
        right = len(word)-1
        while left < right:
            if word[left] != word[right]:
                return False
            left += 1
            right -= 1
        return True

  • 0
    F

    Thanks for your idea! I do the same thing following your way, and here is my JAVA code:

    public List<List<Integer>> palindromePairs2(String[] words) {
        List<List<Integer>> lists = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            map.put(words[i], i);
        }
        for (String word : words) {
            String reverse = new StringBuilder(word).reverse().toString();
            if (map.containsKey(reverse) && map.get(word) != map.get(reverse)) {
                lists.add(new ArrayList<>(Arrays.asList(map.get(word), map.get(reverse))));
            }
            for (int i = 0; i < word.length(); i++) {
                String tmp1 = new StringBuilder(word.substring(0, i)).reverse().toString();
                String tmp2 = reverse.substring(0, i);
                if (map.containsKey(tmp1) && isPalindrome(word.substring(i))) {
                    lists.add(new ArrayList<>(Arrays.asList(map.get(word), map.get(tmp1))));
                }
                if (map.containsKey(tmp2) && isPalindrome(reverse.substring(i))) {
                    lists.add(new ArrayList<>(Arrays.asList(map.get(tmp2), map.get(word))));
                }
            }
        }
        return lists;
    }
    
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

Log in to reply
 

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