[Swift]LeetCode1079. 活字印刷 | Letter Tile Possibilities

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

You have a set of tiles, where each tile has one letter tiles[i] printed on it. Return the number of possible non-empty sequences of letters you can make.

Example 1:

Input: "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

Example 2:

Input: "AAABBC"
Output: 188

Note:

1 <= tiles.length <= 7
tiles consists of uppercase English letters.

你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。

示例 1：

输入："AAB"
输出：8
解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。

示例 2：

输入："AAABBC"
输出：188

提示：

1 <= tiles.length <= 7
tiles 由大写英文字母组成

Runtime: 12 ms

Memory Usage: 22.5 MB

 1 class Solution {
 2     func numTilePossibilities(_ tiles: String) -> Int {
 3         let arr:[Character] = Array(tiles)
 4         let len:Int = tiles.count
 5         var cnt:[Character:Int] = [Character:Int]()
 6         var ans:Int = 0
 7         for i in 0..<len
 8         {
 9             cnt[arr[i],default: 0] += 1
10         }
11         var tab:[Int] = [Int]()
12         cnt.dropLast()
13         for val in cnt.values
14         {
15             tab.append(val)
16         }
17         dfs(&tab, &ans)
18         return ans
19     }
20     
21     func dfs(_ tab:inout [Int],_ ans:inout Int)
22     {
23         for i in 0..<tab.count
24         {
25             if tab[i] > 0
26             {
27                 ans += 1
28                 tab[i] -= 1
29                 dfs(&tab,&ans)
30                 tab[i] += 1
31             }
32         }
33     }
34 }
35 
36 //String扩展
37 extension String {
38     //subscript函数可以检索数组中的值
39     //直接按照索引方式截取指定索引的字符
40     subscript (_ i: Int) -> Character {
41         //读取字符
42         get {return self[index(startIndex, offsetBy: i)]}
43     }
44 }

20ms

 1 class Solution {
 2     var memo = [String:Int]()
 3     func helper(_ tiles: String, _ n: Int) -> Int {
 4         guard n > 0 else { return 1 }
 5         var visited = Set<Character>()
 6         var count = 0
 7         for i in 0..<tiles.count {
 8             let index = tiles.index(tiles.startIndex, offsetBy: i)
 9             let char = tiles[index]
10             guard !visited.contains(char) else { continue }
11             visited.insert(char)
12             var newTiles = tiles
13             newTiles.remove(at: index)
14             let key = newTiles + String(n - 1)
15             if memo[key] == nil {
16                 memo[key] = helper(newTiles, n - 1)
17             }
18             count += memo[key]!
19         }
20         return count
21     }
22     
23     func numTilePossibilities(_ tiles: String) -> Int {
24         return (1...tiles.count)
25             .map { helper(tiles, $0) }
26             .reduce(0, +)
27     }
28 }

84ms

 1 class Solution {
 2     func helper(_ tiles: String, _ n: Int) -> Int {
 3         guard n > 0 else { return 1 }
 4         
 5         var visited = Set<Character>()
 6         var count = 0
 7         for i in 0..<tiles.count {
 8             let index = tiles.index(tiles.startIndex, offsetBy: i)
 9             let char = tiles[index]
10             guard !visited.contains(char) else { continue }
11             visited.insert(char)
12             var newTiles = tiles
13             newTiles.remove(at: index)
14             count += helper(newTiles, n - 1)
15         }
16         return count
17     }
18     
19     func numTilePossibilities(_ tiles: String) -> Int {
20         var count = 0
21         for i in 1...tiles.count {
22             count += helper(tiles, i)
23         }
24         return count
25     }
26 }

116ms

 1 class Solution {
 2     
 3     func dfs( freq: inout [Character : Int]) -> Int {
 4     var count = 0
 5     
 6     for letter in freq {
 7         if letter.value > 0 {
 8             count += 1
 9             freq[letter.key]! -= 1
10             count += dfs(freq: &freq)
11             freq[letter.key]! += 1
12         }
13     }
14     return count
15 }
16     
17     func numTilePossibilities(_ tiles: String) -> Int {
18             var freq : [Character : Int] = [:]
19     for tile in tiles {
20         freq[tile, default:0] += 1
21     }
22     
23     return dfs(freq: &freq) 
24     }
25 }

204ms

 1 class Solution {
 2     func numTilePossibilities(_ tiles: String) -> Int {
 3         var cache: Set<String> = Set<String>()
 4              
 5         numFor(tile: tiles, cache: &cache)
 6         
 7         return cache.count
 8     }
 9     
10     private func numFor(tile: String, cache: inout Set<String>) {
11         // print("tile=(tile), cache=(cache)")
12         guard cache.contains(tile) == false else {
13             return 
14         }
15         guard tile.count > 0 else {
16             return
17         }
18         
19         cache.insert(tile)
20         
21         for i in 1 ..< tile.count {
22             var temp = tile
23             let char = temp.remove(at: tile.index(tile.startIndex, offsetBy: i))
24             numFor(tile: String(char), cache: &cache)
25             numFor(tile: temp, cache: &cache)
26             numFor(tile: String(char) + temp, cache: &cache)
27         }
28     }
29 }

212ms

 1 class Solution {
 2     func numTilePossibilities(_ tiles: String) -> Int {
 3         var chars = Array(tiles)
 4         var set = Set<String>()
 5         var isVisited = [Bool](repeating: false, count: tiles.count)
 6         var result = 0
 7         findSeq(chars, &set, &isVisited, "")
 8         // print(set)
 9         return set.count
10     }
11     
12     fileprivate func findSeq(_ chars: [Character], _ set: inout Set<String>, _ isVisited: inout [Bool], _ path: String) {
13         var count = 0
14         for item in isVisited {
15             if item == false { count += 1 }
16         }
17         if count == 0 { return }
18         
19         
20         for i in 0...chars.count-1 {
21             guard !isVisited[i] else {
22                 continue 
23             }
24             let curr = path + String(chars[i])
25             if !set.contains(curr) { set.insert(curr) }
26             isVisited[i] = true
27             findSeq(chars, &set, &isVisited, curr)
28             isVisited[i] = false
29         }
30     }
31 }

224ms

 1 class Solution {
 2     var res = Set<String>()
 3     func helper(_ chars: [Character], _ n: Int, _ selected: String) {
 4         guard n > 0 else {
 5             res.insert(selected)
 6             return
 7         }
 8         for i in 0..<chars.count {
 9             var newChars = chars
10             let newSelect = newChars.remove(at: i)
11             helper(newChars, n - 1, selected + String(newSelect))
12         }
13         
14     }
15     func numTilePossibilities(_ tiles: String) -> Int {
16         let chars = Array(tiles)
17         
18         for i in 1...tiles.count {
19             helper(chars, i, "")
20         }
21         return res.count
22     }
23 }

232ms

 1 class Solution {
 2     private var sets = Set<String>()
 3     func backtrack(_ chars: inout [Character], _ i: Int) {
 4         if (i >= 1) {
 5             let str = String(chars[0..<i])
 6             sets.insert(str)
 7         }
 8         if i == chars.count { return }
 9         for j in i ..< chars.count {
10             chars.swapAt(i, j)
11             backtrack(&chars, i + 1)
12             chars.swapAt(i, j)
13         }
14     }
15 
16     func numTilePossibilities(_ tiles: String) -> Int {
17         var chars = Array(tiles)
18         backtrack(&chars, 0)
19         return sets.count
20     }
21 }