LeetCode-336. 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:

Input: ["abcd","dcba","lls","s","sssll"]

Output: [[0,1],[1,0],[3,2],[2,4]]

Explanation: The palindromes are

​

​["dcbaabcd","abcddcba","slls","llssssll"]​

​

Example 2:

Input: ["bat","tab","cat"]

Output: [[0,1],[1,0]]

Explanation: The palindromes are ​

​["battab","tabbat"]​

​

​

​题解：基本思路就是两两判断，有很多剪枝，懒得加了。。​

​

class Solution {
public:
  bool isPailndrome (string s) {
    int n = s.length();
    int l = 0, r = n - 1;
    while (s[l] == s[r]) {
      l++;
      r--;
    }
    if (l <= r) {
      return false;
    }
    return true;
  }
  vector<vector<int>> palindromePairs(vector<string>& words) {
    vector<vector<int>> ans;
    int n = words.size();
    for (int i = 0; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) {
        if (words[i][0] != words[j][words[j].length() - 1] && words[i][words[i].length() - 1] != words[j][0] && words[i] != "" && words[j] != "") {
          continue;
        }
        string s1 = words[i] + words[j];
        string s2 = words[j] + words[i];
        if (isPailndrome(s1) == true) {
          vector<int> tmp;
          tmp.push_back(i);
          tmp.push_back(j);
          ans.push_back(tmp);
        }
        if (isPailndrome(s2) == true) {
          vector<int> tmp;
          tmp.push_back(j);
          tmp.push_back(i);
          ans.push_back(tmp);
        }
      }
    }
    return ans;
  }
};