【HARD】Palindrome Pairs

发布于: 2019-02-01 23:15
阅读: 59
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/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"]

分析过程

  • 输入:字符串数组
  • 输出:可以两两组成回文的组合下标
  • 思路:最简单的是遍历左右可能的组合,拼起来后检查是否是回文,但时间复杂度过高。利用回文的特性,可以针对字符串的子字符串进行分析。
    • 组成回文无非一下几种情况:
      • [ABC][CBA]
      • [ABC][BA]
      • [ABCDC][BA]
    • 他们共同的特征是,在输入的字符串中能够找到这个字符串的某个子串的逆序。
    • 只要遍历当前字符串的所有子串,找到这个子串中的回文,然后再在输入中寻找剩余部分的逆序即可。
    • 上面提到的回文子串可以是空字符串、一个字母的字符串、或多个字母的回文。
    • 需要注意的是,自己不能和自己组成回文,这种情况需要排除。

解决方法

extension String {
    
    // 是否是回文
    var isPalindrome: Bool {
        let size = self.count;
        let startIndex = self.utf8.startIndex
        for i in 0..<size / 2 {
            if self.utf8[self.utf8.index(startIndex, offsetBy: i)] != self.utf8[self.utf8.index(startIndex, offsetBy: size - i - 1)] {
                return false;
            }
        }
        return true;
    }
}

class Solution {
    func palindromePairs(_ words: [String]) -> [[Int]] {
        // 存放结果
        var res = [[Int]]()
        // 建立存放字符串对应的索引,用于输出
        var indexMap = [String: Int]()
        for (i, str) in words.enumerated() {
            indexMap[str] = i
        }
        // 遍历每个字符串
        for i in 0..<words.count {
            let str = words[i]
            // 空字符串和其他回文字符串能够拼成回文
            guard str != "" else {
                for k in 0..<words.count {
                    guard k != i else {
                        continue
                    }
                    if words[k].isPalindrome {
                        res.append([i, k])
                    }
                }
                continue
            }
            // 拆字符串,以 j 为分界线把字符串拆成两部分 对字符串的每一种分隔方法都遍历
            for j in 0..<str.count {
                let part1 = String(str.prefix(j))
                let part2 = String(str.suffix(str.count - j))
                // 如果第二部分是回文
                if part2.isPalindrome {
                    // 找第一部分的逆序,如果有,拼在第二部分后面即可构成回文
                    let part1Reversed = String(part1.reversed())
                    if let index = indexMap[part1Reversed], index != i {
                        res.append([i, index])
                    }
                }
                // 如果第一部分是回文
                if part1.isPalindrome {
                    // 找第二部分的逆序,如果有,拼在第一部分前面即可构成回文
                    let part2Reversed = String(part2.reversed())
                    if let index = indexMap[part2Reversed], index != i {
                        res.append([index, i])
                    }
                }
                // 这里把空字符串看做是合法回文,对于空子串直接找另一部分的逆序即可
            }
        }
        
        return res
    }
}

Thanks for reading.

All the best wishes for you! 💕