首页 > 代码库 > [LeetCode]Palindrome Pairs

[LeetCode]Palindrome Pairs

2024-11-24 07:43:39   202人阅读

题目：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"]

题意：给定一些不懂的单词，找到所有的两个单词能拼成回文串的组合。

思路：

为了查找更快速，考虑使用map，将string作为key，这样就可以直接匹配string了；

但是这样要怎么找回文组合呢？

从上面的例子可以看出：

1.可能两个单词相互是逆序的关系，那样就是两组回文组合；

2.可能一个单词和另一个单词的一部分是相互逆序的关系，这样只能得到一个回文组合。

基本就只有这两种情况，但是可能会有一些边界情况需要注意：

1.空串的情况，空串和自身回文的单词可以组成回文；

2.自身是回文的单词不要和自己组合在一起了。

这样可以的到算法，主要思路：

1.得到一个所有单词逆序的集合并且和原来位置的下标绑定到一起；

2.遍历每个单词，并且找到每个单词的子串(begin,i)和(i+1,end)；然后使用map去和逆序的单词匹配能匹配上，再看剩下的一部分是否是回文的，是回文的则是一个合法的组合。

于是就可以得到下面的程序：

vector<vector<int>> palindromePairs(vector<string>& words){
    unordered_map<string, int>rwords;//key是word的逆序，value是其对应的单词的下标
    vector<vector<int>>result;//返回结果
    for (size_t i = 0; i < words.size(); ++i){
        string key = words[i];
        reverse(key.begin(), key.end());//逆置字符串
        rwords[key] = i;//加入map中
    }
    //边界情况，当存在空串时，需判断字符串本身是否回文
    if (rwords.find("") != rwords.end()){
        int zero = rwords[""];//空串的位置
        for (size_t i = 0; i < words.size(); ++i){
            if (i != zero && isPalindrome(words[i])){
                result.push_back({ (int)i, zero });//排除空串自身
                result.push_back({ zero, (int)i });//排除空串自身
            }
        }
    }
    //找到每个单词的回文组合
    for (size_t i = 0; i < words.size(); i++){
        for (size_t j = 0; j < words[i].size(); j++){
            string left = words[i].substr(0, j);//从j为界分割单词为左右两部分
            string right = words[i].substr(j, words[i].size() - j);
            //查找是否有以左边为逆序的单词，并判断右边是否回文；注意单词本身回文则可能找到自己本身，且空串前面以找过
            if (j && rwords.find(left) != rwords.end() && isPalindrome(right) && rwords[left] != i)result.push_back({ (int)i, rwords[left] });
            //查找是否有以右边为逆序的单词，并判断左边是否回文；j < words[i].size()，左边字符串不可能为空串
            if (rwords.find(right) != rwords.end() && isPalindrome(left) && rwords[right] != i)result.push_back({ rwords[right], (int)i });
        }
    }
    return result;
}

回文相关的算法可以参考这篇博文：

http://www.cnblogs.com/yeqluofwupheng/p/6796747.html

http://www.cnblogs.com/yeqluofwupheng/p/6720384.html

 

[LeetCode]Palindrome Pairs


联系
我们