Microsoft and Google have organized a group of interview questions, you can add administrator VX: sXXZS3998 (note the gold dig), to participate in the discussion and livestream

1. The subject

Given a different set of words, find all the different index pairs (I, j) so that two words in the list, words[I] + words[j], can be concatenated into palindromes.

The sample1: Enter: words = ["abcd"."dcba"."lls"."s"."sssll"] Output: [[0.1], [1.0], [3.2], [2.4]] : can be spliced into palindrome string for ["dcbaabcd"."abcddcba"."slls"."llssssll"] example2: Enter: words = ["bat"."tab"."cat"] Output: [[0.1], [1.0]] : can be spliced into palindrome string for ["battab"."tabbat"] example3: Enter: words = ["a".""] Output: [[0.1], [1.0]]
Copy the code

2.

In this case, violence can be used, that is, the combination of each pair of strings in American TV series can be used to determine whether they can form palindromes. The time complexity is O(n2∗m)O(n^2*m)O(n2∗m), where NNN is the number of strings and MMM is the average length of strings. But obviously, such time complexity is inefficient in practical engineering.

Suppose there are two strings s1S_1S1 and s2S_2S2, s1+ s2S_1 + s_2S1 + S2 is a palindrome string, where the length of the two strings is len1LEN_1LEN1 and LEN2LEN_2LEN2: 1) If len1= Len2LEN_1 = len_2LEN1 = Len2, then s1s_1S1 is the inversion of s2s_2s2. 2) If LEN1 > LEN2LEN_1 > LEN_2LEN1 > Len2, in this case, s1s_1S1 can be split into two parts t1t_1T1 and T2t_2T2, where T1t_1T1 is the inversion of S2s_2S2, 3) If LEN1 < LEN2LEN_1 < LEN_2LEN1 < LEN2, in which case s2s_2S2 is split into two parts t1t_1T1 and t2t_2T2, where T2t_2T2 is the inversion of S1s_1S1, T1t_1t1 is a palindrome string

So, when faced with two strings, we can take the longer of the two strings and split them into two parts, t1t_1T1 and t2t_2t2:

  • When t1T_1T1 is a palindrome string, in case 3), it is only necessary to check whether the t2t_2T2 string contains a flip
  • When t2T_2T2 is a palindrome, case 2), it is only necessary to check whether the t1T_1T1 string contains a flip

So, this is equivalent to checking each string for palindromes, and then flipping the rest to match the other strings. There are two ways to do this:

  • We can use a dictionary tree to store all strings. In the process of query, the substring of the query string is traversed in the dictionary tree in reverse order to judge whether it exists.
  • We can use a hash table to store the flipped string of all strings. In the process of query, we can determine whether the substring with query appears in the hash table, which is equivalent to determining whether its flip exists.

Dictionary tree, also known as word search tree, prefix tree, is a tree structure, the use of string common prefix to reduce the query time, minimize unnecessary string comparison, faster than hash table. The root node contains no characters, and each node except the root node contains only one character. From the root node to a node, the characters on the path are connected to the string corresponding to the node. All children of each node contain different characters.

A simple example is as follows: 1) Build a dictionary tree

2) Find the string “a”

So, here’s the idea:

  • build

The string is reversed; Walk through word to create a node; Word. Substring (j+1) is a palindrome, which is added to the Suffixs list of the object. Note that word is a palindrome and is added to the suffixs list of the root node.

  • To find the

Traverse the word; If word.substring(j) is a palindrome, see if the current node is a word, and if so, add it to the result; 3) If word traversal ends and word ends in word, check the suffixs list of the current node. Case 2)

class Solution {
public:
    struct node {
        int ch[26];
        int flag;
        node() {
            flag = - 1;
            memset(ch, 0.sizeof(ch)); }}; vector<node> tree;void insert(string& s, int id) {
        int len = s.length(), add = 0;
        for (int i = 0; i < len; i++) {
            int x = s[i] - 'a';
            if(! tree[add].ch[x]) { tree.emplace_back(a); tree[add].ch[x] = tree.size() - 1;
            }
            add = tree[add].ch[x];
        }
        tree[add].flag = id;
    }

    int findWord(string& s, int left, int right) {
        int add = 0;
        for (int i = right; i >= left; i--) {
            int x = s[i] - 'a';
            if(! tree[add].ch[x]) {return - 1;
            }
            add = tree[add].ch[x];
        }
        return tree[add].flag;
    }

    bool isPalindrome(string& s, int left, int right) {
        int len = right - left + 1;
        for (int i = 0; i < len / 2; i++) {
            if(s[left + i] ! = s[right - i]) {return false; }}return true;
    }

    vector<vector<int>> palindromePairs(vector<string>& words) {
        tree.emplace_back(node());
        int n = words.size(a);for (int i = 0; i < n; i++) {
            insert(words[i], i);
        }
        vector<vector<int>> ret;
        for (int i = 0; i < n; i++) {
            int m = words[i].size(a);for (int j = 0; j <= m; j++) {
                if (isPalindrome(words[i], j, m - 1)) {
                    int left_id = findWord(words[i], 0, j - 1);
                    if(left_id ! =- 1&& left_id ! = i) { ret.push_back({i, left_id}); }}if (j && isPalindrome(words[i], 0, j - 1)) {
                    int right_id = findWord(words[i], j, m - 1);
                    if(right_id ! =- 1&& right_id ! = i) { ret.push_back({right_id, i}); }}}}returnret; }};Copy the code

Hash table

class Solution {
private:
    vector<string> wordsRev;
    unordered_map<string_view, int> indices;

public:
    int findWord(const string_view& s, int left, int right) {
        auto iter = indices.find(s.substr(left, right - left + 1));
        return iter == indices.end()?- 1 : iter->second;
    }

    bool isPalindrome(const string_view& s, int left, int right) {
        int len = right - left + 1;
        for (int i = 0; i < len / 2; i++) {
            if(s[left + i] ! = s[right - i]) {return false; }}return true;
    }

    vector<vector<int>> palindromePairs(vector<string>& words) {
        int n = words.size(a);for (const string& word: words) {
            wordsRev.push_back(word);
            reverse(wordsRev.back().begin(), wordsRev.back().end());
        }
        for (int i = 0; i < n; ++i) {
            indices.emplace(wordsRev[i], i);
        }

        vector<vector<int>> ret;
        for (int i = 0; i < n; i++) {
            int m = words[i].size(a);if(! m) {continue;
            }
            string_view wordView(words[i]);
            for (int j = 0; j <= m; j++) {
                if (isPalindrome(wordView, j, m - 1)) {
                    int left_id = findWord(wordView, 0, j - 1);
                    if(left_id ! =- 1&& left_id ! = i) { ret.push_back({i, left_id}); }}if (j && isPalindrome(wordView, 0, j - 1)) {
                    int right_id = findWord(wordView, j, m - 1);
                    if(right_id ! =- 1&& right_id ! = i) { ret.push_back({right_id, i}); }}}}returnret; }};Copy the code
  • Time complexity: O(n∗m2)O(n*m^2)O(n∗m2), where NNN is the number of strings and MMM is the average length of strings. For each string, we need O(m2)O(m^2)O(m2) to determine whether all prefixes and suffixes are palindromes, and O(m2)O(m^2)O(m2) O to find whether all prefixes and suffixes are present in a given sequence of strings.
  • Space complexity: O(n×m)O(n×m)O(n×m) O(n×m), where n is the number of strings and m is the average length of strings is the space overhead of the dictionary tree.

Microsoft and Google have organized a group of interview questions, you can add administrator VX: sXXZS3998 (note the gold dig), to participate in the discussion and livestream