【HARD】Palindrome Pairs

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

问题

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[startIndex] != self.utf8[self.utf8.index(startIndex, offsetBy: size - i - 1)] {
                return false;
            }
        }
        return true;
    }
}

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

var result = palindromePairs(strList: ["abcd","dcba","lls","s","sssll"])
result = palindromePairs(strList: ["bat","tab","cat"])

Thanks for reading.

All the best wishes for you! 💕