【求助】虚心请教经典题目摩斯密码思路解法

就是那道很经典的摩斯码题，
input = morse code string,
output 全部英文string的可能性。

EX: input =  “....”
      output = ["EEEE", "II", "SE", "ES", "EIE", "EEI", "IEE", "H"]

/*'A': '.-', 'B': '-...', 'C': '-.-.', 'D': '-..', 'E': '.', 'F': '..-.', 'G': '--.', 'H': '....',
    'I': '..', 'J': '.---', 'K': '-.-', 'L': '.-..', 'M': '--', 'N': '-.', 'O': '---', 'P': '.--.',
    'Q': '--.-', 'R': '.-.', 'S': '...', 'T': '-', 'U': '..-', 'V': '...-', 'W': '.--', 'X': '-..-',
    'Y': '-.--', 'Z': '--..'*/  

自己写了一个，但是实在太乱了，而且有bug修不成，肯定面试的时候用不了，也不好记。
有人说用backtracking, 可是怎么判断中间的substring呢？
我的写法是造一个map，每一个substring morse code作为key，每一个value都是一个list of results corresponding to that morse code，只要查出有一个新letter的话就加进map去，只要是已经出现过的letter就update每一个list里面每一个result, 直到整条morse code扫描完毕。
可是这个做法很慢，space and time heavy。。可是就是搞不懂怎么做好。。请教论坛大神们，私信或者回复这里都行。谢谢啦

麻倉枼 发表于 2018-4-5 03:09
谢谢，好像解决了，很漂亮的解法！

：）谢谢～能否求点大米～?

假定trans是把morse翻译成字母的字典，如trans['.-']='A'

您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

julieusc 发表于 2019-1-27 15:17
想问下楼主如果用backtracking & memorization set的话，时间和空间复杂度分别应该是多少？

我来说说我的想法。

加上memorization，DFS被叫的次数会变为 O(N^2)

但HashMap里的总共的方案，仍然会有O（2^N）个。最坏情况是
1, 1 方案
2, 2 方案
3, 4 方案
4, 8 方案
...
方案里面的每个String都会有长度N。

因此我认为总共的空间复杂度O（2^N），时间复杂度是O(N^2 + N*2^N)

补充内容 (2019-1-28 05:55):
空间复杂度漏了应为O(N*2^N)

谢谢，好像解决了，很漂亮的解法！

你这个方法不就是挺好的 你的这个解法不就是memoization+recursion么

dtccx 发表于 2018-4-4 18:36
你这个方法不就是挺好的 你的这个解法不就是memoization+recursion么

做出bug了，做法还是DP（但是自己是DP渣），本来以为用LC 91改一下就行了，结果发现太多edge cases，最后改成一坨屎了，脑爆了做不出来

foreveriii3 发表于 2018-4-4 18:18
：）谢谢～能否求点大米～?

已经给了，大神觉得够不够？

麻倉枼 发表于 2018-4-5 07:41
做出bug了，本来以为用LC 91改一下就行了，结果发现太多edge cases，最后改成一坨屎了，脑爆了做不出来

lol，学累了来瓶红牛，还原你一个天才大脑。但是mountain dew更好喝诶

dtccx 发表于 2018-4-4 18:43
lol，学累了来瓶红牛，还原你一个天才大脑。但是mountain dew更好喝诶

我做这题生病了，现在还有点脑痛。。智商捉急啊

麻倉枼 发表于 2018-4-5 07:44
我做这题生病了，现在还有点脑痛。。智商捉急啊

摸摸，注意身体，身体是革命的本钱