求问一个 G家 的经典题，最佳字符串压缩

compress string和uncompress string。 比如说 aaaababa可以压缩成4[a]2[ba], 也可 以是3[a]2[ab]a. 找最优压缩办法

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

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

iley/QQ/em34.gif" smilieid="112" border="0" alt="" />

LZ咱们俩差不多同一天onsite。。第一题就是LC471啊，就是用DP，dp[i][j]就是从i到j的最佳encode方式，那么长度小于等于3的时候，不做任何处理，就存当前的s.substring(i,j)。（因为长度上3[a]还不如aaa）
如果长度大于3，那么就再遍历从i到j（也就是当前的子串），看这个区间里面能否有可以encode的字符串，还有可能的两个求和。比如aaaaaa，这个substring就可以压缩成6[a]，当然之前长度为4遍历的时候可能会出现4[a]aa这种情况，比对一下哪个长度更好即可。那么这个算法的复杂度是On^3吧。

第二题这种策略题目，leetcode就有个guess number。所以要先明确单词长度是不是达成共识，我猜应该是的。暴力方法就是每个位置遍历26个字母，在分数出现变化的时候（比如aa变成ba分数减了1，那肯定说明第一个位置是a），最坏情况是26^n。这个复杂度很高，比三层楼还要高。
然后再从简单的case出发，比如单词长度n=1，那么按照给好的条件怎么都要worst case是26。所以如果这题没有给出想的单词的范围，比如给个set当字典，或者其他条件的话，那除非绑架他老婆逼他说出单词内容否则没有什么更好的办法了。因为从条件上面看，对方不给条件，那我们也只好暴力破解了。
突然想到个优化，就是比如n = 2的情况，那一次猜两个，比如aa，如果得1分，改成bb，这时候如果还是1分，那答案就是ab或者ba了，所以得多少分意味着当前猜测的结果里面有多少个字母。那比如n个字符的话，我第一次猜n个a，比如拿到x分，第二次猜n个b，拿到y分，说明这里面有x个a和y个b，26个字母扫一遍，会拿到一个统计，这个单词里面有几个a，几个b，几个s，几个m之类的，那么单词一定就是这么几个字母的组合，用所有的permutation去轰就可以了。复杂度是n!，这样的话比26^n会小很多，我们也不需要对出词的人做一些暴力举动，世界更和平了。

以上是我对这两道题的思考过程，第二题因为没见过稍微拐了点儿弯，不过permutation算是我能想出来的最优解了。还有几个小时就要飞向mtv了，给自己和LZ都加加油。

补充内容 (2016-12-18 00:54):
guess number好像和第二题没啥关系。。

忆梦前尘 发表于 2016-12-18 16:52
LZ咱们俩差不多同一天onsite。。第一题就是LC471啊，就是用DP，dp[j]就是从i到j的最佳encode方式，那么长度 ...

感谢回复哈~

leetcode 又出新题了啊..都加油哈

googleonsite 发表于 2016-12-18 01:10
感谢回复哈~

leetcode 又出新题了啊..都加油哈

是啊，不过我觉得挺难想的，第一题的DP和burst balloons差不多。看面经第一题没考到那么难，一般会考怎么decode，然后decode有非法字符怎么办。

忆梦前尘 发表于 2016-12-18 17:12
是啊，不过我觉得挺难想的，第一题的DP和burst balloons差不多。看面经第一题没考到那么难，一般会考怎么 ...

你说的decode非法字符是什么意思啊 该怎么处理呢

忆梦前尘 发表于 2016-12-18 16:52
LZ咱们俩差不多同一天onsite。。第一题就是LC471啊，就是用DP，dp[j]就是从i到j的最佳encode方式，那么长度 ...

第二题 如果给了个字典的话 还有一种方法是猜一个词m，给出x个相同，然后到字典里，如果一个词跟m没有x个相同letter，就把这个词remove掉。这种方法不好说complexity，不过貌似也可以

wsrrzxl 发表于 2016-12-18 12:19
你说的decode非法字符是什么意思啊 该怎么处理呢

比如3a2b，出来aaabb，面试官说，我33a2b出来就是要把3给变成3个这样就很头疼，可以先把要decode的数字处理一下，然后再按照原计划执行

忆梦前尘 发表于 2016-12-18 16:52
LZ咱们俩差不多同一天onsite。。第一题就是LC471啊，就是用DP，dp[j]就是从i到j的最佳encode方式，那么长度 ...

感谢你的回复啊。
我发现第一题还是不太懂到底是什么个意思……我打算先做一些简单的再说。

草袋豆子 发表于 2016-12-20 10:50
感谢你的回复啊。
我发现第一题还是不太懂到底是什么个意思……我打算先做一些简单的再说。

对，没关系面试题目最近都不难的

忆梦前尘 发表于 2016-12-21 03:10
对，没关系面试题目最近都不难的

多谢！ 希望你的面试一切顺利。