khinboon
BAN USERIn Swift, based on Antonio081014 answer.
The time complexity based on benchmark is fib(N) but I couldn't fully explain why? Anyone have any insight on this?
let text = "122222222226"
let characters = text.characters
func map(characters: [Character]) -> String.CharacterView? {
let table: [String: String] = [
"1" : "a",
"2" : "b",
"3" : "c",
"4" : "d",
"5" : "e",
"6" : "f",
"7" : "g",
"8" : "h",
"9" : "i",
"10" : "j",
"11" : "k",
"12" : "l",
"13" : "m",
"14" : "n",
"15" : "o",
"16" : "p",
"17" : "q",
"18" : "r",
"19" : "s",
"20" : "t",
"21" : "u",
"22" : "v",
"23" : "w",
"24" : "x",
"25" : "y",
"26" : "z",
]
return table[String(characters)]?.characters
}
func decode(prefix: String.CharacterView, characters: String.CharacterView) -> Set<String> {
var set = Set<String>()
if characters.isEmpty {
set.insert(String(prefix))
return set
}
let startIndex = characters.startIndex
let character = characters[startIndex]
if let mappedCharacter = map([character]) {
set.unionInPlace(decode(prefix + mappedCharacter, characters: characters.suffixFrom(startIndex.successor())))
}
if characters.count >= 2 {
let nextIndex = startIndex.successor()
let nextCharacter = characters[nextIndex]
if let mappedCharacter = map([character, nextCharacter]) {
set.unionInPlace(decode(prefix + mappedCharacter, characters: characters.suffixFrom(nextIndex.successor())))
}
}
return set
}
print(decode("".characters, characters: characters))
Sorry for the double posting. I registered an account and post the same answer.
- khinboon December 22, 2015