09 -- palindrome pair

Catalog

One 、 What is palindrome pair

Two 、 subject

3、 ... and 、 Their thinking

Palindrome + Flip

  Two layers of for loop

---

Github link

---

One 、 What is palindrome pair

1. The palindrome is right , It's a symmetric string , such as

"a"

"aba"

"aabb"

Two 、 subject

Give a group Different from each other 's words , Find out all Different The index of (i, j), Make two words in the list , words[i] + words[j] , Can be spliced into palindrome string .

Example 1：

Input ：words = ["abcd","dcba","lls","s","sssll"]
Output ：[[0,1],[1,0],[3,2],[2,4]] 
explain ： The palindrome string that can be spliced is ["dcbaabcd","abcddcba","slls","llssssll"]

3、 ... and 、 Their thinking

1. Palindrome + Flip

• hold words All strings in the array are flipped first , Then put it in a dictionary [String: Int]
• Yes words Array traversal
• If you traverse to an empty array , And the dictionary contains key The palindrome is right , Then add the answer
• Complexity ：O(n^2)

for example ：

1. words Flip , Add a dictionary , Then you will get the dictionary

[["dcba": 0], ["abcd": 1], ["sll": 2], ["s": 3], ["llsss": 4]]

2. An array words = ["abcd","dcba","lls","s","sssll"] Traversal

（1） For example, the current subscript is 2, Then the string is “lls”

          From the subscript for 0 Start , Segmentation ,

        left = "" , right = "lls", although left For palindromes to , but   There is no... In the dictionary “lls” by key, Continue to split

        left = "l", right = "ls", although left For palindromes to , But not in the dictionary “ls” by key, Continue to split

        left = "ll", right = "s", left The palindrome is right , The dictionary also contains “s” by key, The subscript index = 2

         ["s": 3] Medium value = 3

        Because the symmetrical section （left）, It must be placed in the middle , The new string spliced together can also be a palindrome pair

        So the string of the current subscript is placed after

        that [3 , 2] The string composed of subscripts is “s” + "lls" == “slls”, It's palindrome yeah

  （2）  For example, the current subscript is 4, Then the string is “sssll”

         From the subscript for 0 Start , Segmentation ,

        left = "" , right = "sssll", although left For palindromes to , but   There is no... In the dictionary “sssll” by key, Continue to split

        left = "s", right = "ssll", although left For palindromes to , But not in the dictionary “ssll” by key, Continue to split

        left = "ss", right = "sll", left The palindrome is right , The dictionary also contains “sll” by key, The subscript index = 4

         ["sll": 2] Medium value = 2

        Empathy ：

         Because the symmetrical section （left）, It must be placed in the middle , The new string spliced together can also be a palindrome pair

        So the string of the current subscript is placed after

        that [2, 4] => lls + sssll + = llssssll  => It's palindrome yeah

（3） Empathy ：

        If the symmetrical section is （right） part , Then the string of the current subscript should be placed in front of

        Put it all together [ index, dict[right]]     

Code ：

// Dictionary method 
    func palindromePairs(_ words: [String]) -> [[Int]] {
        var dict = [String: Int]()
        var res = [[Int]]()
        
        words.enumerated().forEach { (index, str) in
            dict[String(str.reversed())] = index
        }
        
        for (index, s) in words.enumerated() {
            if s.isEmpty {
                dict.forEach { (Str, idx) in
                    if checkIsOK(Str) && index != idx {
                        res.append([index,idx])
                    }
                }
            }
            
            for j in 0..<s.count {
                let mid = s.index(s.startIndex, offsetBy: j)
                let leftPart = String(s[..<mid])
                let rightPart = String(s[mid...])
                
                if checkIsOK(leftPart) && dict[rightPart] != nil && dict[rightPart] != index {
                    res.append([dict[rightPart]!, index])
                }
                if checkIsOK(rightPart) && dict[leftPart] != nil && dict[leftPart] != index {
                    res.append([index, dict[leftPart]!])
                }
            }
        }
        
        return res
    }

    func checkIsOK(_ s: String) -> Bool {
        return s == String(s.reversed())
    }

  Two layers of for loop

Add strings one by one , Then try to adjust left and right , Concatenate new strings , Determine whether the new string is a palindrome pair , This kind of thinking is relatively easy to understand

Complexity ： O(n^2)

Code ：

//  Splicing method 
    func palindromePairsTimeout(_ words: [String]) -> [[Int]] {
        let n = words.count
        var res = [[Int]]()
        
        for i in 0..<n-1 {
            let str1 = words[i]
            for j in i+1..<n {
                let str2 = words[j]
                if checkIsOK(str1 + str2) {
                    res.append([i,j])
                }
                if checkIsOK(str2 + str1) {
                    res.append([j,i])
                }
            }
        }
        
        return res
    }
    
    func checkIsOK(_ s: String) -> Bool {
        return s == String(s.reversed())
    }