[Swift]LeetCode267.回文全排列II$PalindromePermutationII

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10230174.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:

Given s = "aabb", return ["abba", "baab"].

Given s = "abc", return [].

Hint:

If a palindromic permutation exists, we just need to generate the first half of the string.
To generate all distinct permutations of a (half of) string, use a similar approach from: Permutations II or Next Permutation.

给定的字符串S，回报所有的palindromic置换（没有duplicates）的信息。返回的列表，如果没有空palindromic -可以排列形式。

例如：

给定s = "aabb",返回的 ["abba", "baab"].

给定 s = "abc",，返回 [ ]。

提示：

如果一palindromic排列是否，我们只需要两个Generate的第一个字符串。
Generate置换成不同的两个全（半）的字符串，用相似的方法：Permutations II 或者 Next Permutation.。

 1 class Solution {
 2     func generatePalindromes(_ s:String) -> [String]{
 3         var res:Set<String> = Set<String>()
 4         var m:[Character:Int] = [Character:Int]()
 5         var t:String = ""
 6         var mid:String = ""
 7         for a in s.characters
 8         {
 9             m[a] = 1
10         }
11         for (key, val) in m
12         {
13             if val % 2 == 1
14             {
15                 mid.append(key)
16             }
17             var str:String = String()
18             for i in 0..<val/2
19             {
20                 str.append(key)
21             }
22             t += str
23             if mid.count > 1
24             {
25                 return []
26             }
27         }
28         permute(&t, 0, mid,&res);
29         return Array(res)
30     }
31     
32     func permute(_ t:inout String,_ start:Int,_ mid:String,_ res:inout Set<String>)
33     {
34         if start >= t.count
35         {
36             let str:String = String(t.reversed())
37             res.insert(t + mid + str)
38         }
39         for i in start..<t.count
40         {
41             if i != start && t[i] == t[start]
42             {
43                 continue
44             }
45             var temp:Character
46             temp = t[start]
47             t[start] = t[i]
48             t[i] = temp
49             
50             permute(&t, start + 1, mid, &res)
51             
52             temp = t[start]
53             t[start] = t[i]
54             t[i] = temp
55         }
56     }
57 }
58 
59 extension String {        
60     //subscript函数可以检索数组中的值
61     //直接按照索引方式截取指定索引的字符
62     subscript (_ i: Int) -> Character {
63         //读取字符
64         get {return self[index(startIndex, offsetBy: i)]}
65         
66         //修改字符
67         set
68         {
69             var str:String = self
70             var index = str.index(startIndex, offsetBy: i)
71             str.remove(at: index)
72             str.insert(newValue, at: index)
73             self = str
74         }
75     }
76 }