Accepted short Java solution using HashMap


  • 33
    N
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> pairs = new LinkedList<>();
        if (words == null) return pairs;
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; ++ i) map.put(words[i], i);
        for (int i = 0; i < words.length; ++ i) {
            int l = 0, r = 0;
            while (l <= r) {
                String s = words[i].substring(l, r);
                Integer j = map.get(new StringBuilder(s).reverse().toString());
                if (j != null && i != j && isPalindrome(words[i].substring(l == 0 ? r : 0, l == 0 ? words[i].length() : l)))
                    pairs.add(Arrays.asList(l == 0 ? new Integer[]{i, j} : new Integer[]{j, i}));
                if (r < words[i].length()) ++r;
                else ++l;
            }
        }
        return pairs;
    }
    
    private boolean isPalindrome(String s) {
        for (int i = 0; i < s.length()/2; ++ i)
            if (s.charAt(i) != s.charAt(s.length()-1-i))
                return false;
        return true;
    }

  • 7

    Good idea. I hadn't thought about using two pointers to simplify the suffix/prefix stuff. Although I'm not sure if it counts as a simplification—it definitely makes code shorter, but it also makes it a bit harder to read.

    One minor note, though: you shouldn't ever use LinkedList except when you need fast insertions/deletions, which is not the case here. An ArrayList would do just fine, use less memory and provide better performance too.


  • 0
    N

    Thanks for useful notes


  • 0
    S

    Say n is the number of words and k is the length a word. For each of n words, it needs to reverse a substring of length < k, need to do it for each sub positions of k, figuring out if it is a palindrome (k). So I think the complexity is n k^3


  • 0
    L

    I think it's O(nk^2), get substring and check palindrome needs O(2k) not O(k^2)


  • 0
    H

    new StringBuilder(s).reverse().toString() needs O(k)?


  • 0
    J

    very good idea.


  • 0
    M

    Don't you think some pairs will be repeated. For instance abcd and acbd both these words will generate pairs with each other.


  • 0
    G

    Looks like in each iteration, you find the words can be concated both before and after the word to be palindrome, is it necessary? As you will check all the words in the words list, That combination would be added later, right?


  • 0
    B

    use two pointer is quite a good idea.
    the cpp version based on your idea

    class Solution {
    public:
        vector<vector<int>> palindromePairs(vector<string>& words) {
            vector<vector<int> >res;
            unordered_map<string,int> mp;
            for(int i=0;i<words.size();i++) mp.insert(make_pair(words[i],i));
            for(int i=0;i<words.size();i++){
                string w =words[i];
                int l=0,r=0;
                while(l<=r){
                    string s = w.substr(l,r-l);
                    string rs(s.rbegin(),s.rend());
                    int j = mp.count(rs)>0?mp[rs]:-1;
                    if(i!=j && j>=0 && isPal(l==0?w.substr(r):w.substr(0,l)) )
                        res.push_back(l==0?vector<int>{i,j}:vector<int>{j,i});
                    if(r<w.size()) r++;
                    else l++;
                }
            }
            return res;
        }
    private:
        bool isPal(string&& s){
            string::iterator first = s.begin(),end = s.end();
            while(first!=end&&first!=--end){
                if(*(first++)!=*end) return false;
            }
            return true;
        }
    };
    

Log in to reply
 

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