leetcode 336. Palindrome Pairs 回文数字符串对 + Map加速暴力查询

绝地灬酷狼 2022-06-07 01:13 121阅读 0赞

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”\]

这道题暴力求解肯定超时，我先了好久没有想到更好的办法，网上看了个答案，它是使用HashMap做查询加速，本质还是循环来实现。

**本体需要注意的地方是，要考虑到空字符串的特殊情况，所以内层循环是从0开始的，这个时候会造成重复，所以要使用set来保存结果**

代码如下：

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.HashSet;
    import java.util.List;
    import java.util.Map;
    import java.util.Set;
    
    
    /*
     * 使用暴力循环求解肯定超时，就是不断地拆解一个字符串，然后查询等等
     * 
     * 利用字典wmap保存单词 -> 下标的键值对
     * 遍历单词列表words，记当前单词为word，下标为idx：
     * 1). 若当前单词word本身为回文，且words中存在空串，则将空串下标bidx与idx加入答案
     * 2). 若当前单词的逆序串在words中，则将逆序串下标ridx与idx加入答案
     * 3). 将当前单词word拆分为左右两半left，right。
     *   3.1) 若left为回文，并且right的逆序串在words中，则将right的逆序串下标rridx与idx加入答案
     *   3.2) 若right为回文，并且left的逆序串在words中，则将left的逆序串下标idx与rlidx加入答案
     * 
     * */
    class Solution 
    {
        
        public List<List<Integer>> palindromePairs(String[] words) 
        {
            if(words==null || words.length<=0)
                return new ArrayList<List<Integer>>();      
            Map<String, Integer> map=new HashMap<>();
            Set<List<Integer>> set=new HashSet<>();
    
            //记录查询下标
            for(int i=0;i<words.length;i++)
                map.put(words[i], i);
    
            for(int i=0;i<words.length;i++)
            {
                for(int j=0;j<=words[i].length();j++)
                {
                    String left=words[i].substring(0,j);
                    String right=words[i].substring(j);
                    if(isPalindrome(left))
                    {
                        int one=map.getOrDefault(new StringBuilder(right).reverse().toString(), -1);
                        if(one!=-1 && one!=i)
                        {
                            List<Integer> list=new ArrayList<>();
                            list.add(one);
                            list.add(i);
                            set.add(list);
                        }
                    }               
                    if(isPalindrome(right))
                    {
                        int one=map.getOrDefault(new StringBuilder(left).reverse().toString(), -1);
                        if(one!=-1 && one!=i)
                        {
                            List<Integer> list=new ArrayList<>();
                            list.add(i);
                            list.add(one);
                            set.add(list);
                        }
                    }
                }
            }
            List<List<Integer>> res=new ArrayList<>(set);
            return res;
        }
    
    
    
        /*
         * 暴力循环求解
         * */
        public List<List<Integer>> palindromePairsByBaoLi(String[] words) 
        {
            List<List<Integer>> res=new ArrayList<>();
            if(words==null || words.length<=0)
                return res;
            for(int i=0;i<words.length;i++)
            {
                for(int j=i+1;j<words.length;j++)
                {
                    if(words[i].length()==words[j].length())
                    {
                        if(isPalindrome(words[i]+words[j]))
                        {
                            List<Integer> one=new ArrayList<>();
                            one.add(i);
                            one.add(j);
                            res.add(one);
    
                            List<Integer> one1=new ArrayList<>();
                            one1.add(j);
                            one1.add(i);
                            res.add(one1);
                        }
                    }else 
                    {
                        if(isPalindrome(words[i]+words[j]))
                        {
                            List<Integer> one=new ArrayList<>();
                            one.add(i);
                            one.add(j);
                            res.add(one);
                        }
                        if(isPalindrome(words[j]+words[i]))
                        {
                            List<Integer> one=new ArrayList<>();
                            one.add(j);
                            one.add(i);
                            res.add(one);
                        }
                    }
                }
            }
            return res;
        }
    
        public boolean isPalindrome(String s) 
        {
            int i=0,j=s.length()-1;
            while(i<j)
            {
                if(s.charAt(i)!=s.charAt(j))
                    return false;   
                i++;
                j--;
            }       
            return true;
        }
    }

下面是C++的做法

本质上还是暴力去做，不过使用了Map等数据机构来加速计算

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        vector<vector<int>> palindromePairs(vector<string>& words) 
        {
            set<vector<int>> res;
            unordered_map<string, int> index;
            for (int i = 0; i < words.size(); i++)
                index[words[i]] = i;
    
            for (int i=0;i<words.size();i++)
            {
                string one = words[i];
                for (int j = 0; j <= one.length(); j++)
                {
                    string left = one.substr(0,j);
                    string right = one.substr(j);
                    if (isPalindrome(left) == true)
                    {
                        string tmp = right;
                        reverse(tmp.begin(), tmp.end());
                        if (index.find(tmp) != index.end() && index[tmp] != i)
                            res.insert({ index[tmp],i });
                    }
    
                    if (isPalindrome(right) == true)
                    {
                        string tmp = left;
                        reverse(tmp.begin(), tmp.end());
                        if (index.find(tmp) != index.end() && index[tmp] != i)
                            res.insert({ i,index[tmp] });
                    }
                }
            }
            return vector<vector<int>>(res.begin(),res.end());
        }
    
        bool isPalindrome(string s)
        {
            int i = 0, j = (int)s.length() - 1;
            while (i < j)
            {
                if (s[i] != s[j])
                    return false;
                i++;
                j--;
            }
            return true;
        }
    };