LeetCode: Palindrome Pairs

LeetCode: 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”]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        if (words == null || words.length < 2) {
            return Collections.emptyList();
        }

        List<List<Integer>> result = new ArrayList<>();
        Map<String, Integer> dict = new HashMap<>();
       
        for (int i = 0; i < words.length; i++) {
            dict.put(words[i], i);
        
        }

        for (int i = 0; i < words.length; i++) {
            String a = words[i];
            String reverse = getReverse(a);
            if (isPalindrome(a)) {
                if (dict.containsKey("") && !a.equals("")) {
                    result.add(getPair(i, dict.get("")));
                    result.add(getPair(dict.get(""), i));
                }
            } 
            if (dict.containsKey(reverse) && !reverse.equals(a)) {
                result.add(getPair(i, dict.get(reverse)));
            } 
                for (int x = 1; x < a.length(); x++) {
                    String right = a.substring(x);
                    String left = a.substring(0, x);
                    String rl = getReverse(left);
                    String rr = getReverse(right);
                    if (isPalindrome(right) && dict.containsKey(rl)) {
                        result.add(getPair(i, dict.get(rl)));
                    }
                    if (isPalindrome(left) && dict.containsKey(rr)) {
                        result.add(getPair(dict.get(rr), i));
                    }
                }
            
        }

      
        return result;
    }



    private boolean isSingleCharString(String s) {
        if (s == null || s.isEmpty()) {
            return false;
        }
        char c = s.charAt(0);
        for (int i = 1; i < s.length(); i++) {
            if (c != s.charAt(i)) {
                return false;
            }
        }
        return true;
    }

    private boolean isPalindrome(String s) {
        if (s == null || s.isEmpty()) {
            return true;
        }
        int a = 0;
        int b = s.length() - 1;
        while (a < b) {
            if (s.charAt(a) != s.charAt(b)) {
                return false;
            }
            a++;
            b--;
        }
        return true;
    }

    private String getReverse(String a) {
        StringBuilder sb = new StringBuilder(a);
        return sb.reverse().toString();
    }

    private List<Integer> getPair(int a, int b) {
        List<Integer> result = new ArrayList<>();
        result.add(a);
        result.add(b);
        return result;
    }
}