search

zhedahht / CodingInterviewChinese2

《剑指Offer：名企面试官精讲典型编程面试题》第二版源代码
Other
5.32k stars 2.17k forks source link

面试题19，复杂度高的可怕 #34

Open YuaCC opened 5 years ago

YuaCC commented 5 years ago

每遇到一个*，就会产生一个分支，，指数级别的复杂度。 用编译原理里面的方法进行优化也好，用动态规划来做也行。如此暴力的解决方式会给人误导的。

YuaCC commented 5 years ago

Test("Test31", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac", "a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*b", false); 这个输入会导致程序卡死

GreyLove commented 5 years ago

确实是，复杂度很高

Nju-Ben commented 2 years ago

这个题复杂度确实太高了，leetcode通过不了