問(wèn)題從谷歌的一道面試題開(kāi)始：
給你一個(gè)英語(yǔ)的語(yǔ)句支竹，比如"London bridge is falling down"剖淀，把它完全倒裝過(guò)來(lái)督勺，"down falling is bridge London"注簿，如何不使用額外的存儲(chǔ)空間完成這個(gè)倒裝過(guò)程待锈？
第一步湖员，先將整個(gè)句子看成是一個(gè)完整的字符串贫悄，以字母為單位頭尾對(duì)調(diào)，這樣上面的句子就變成了下面這樣一個(gè)亂七八糟的字符串：
“nwod gnillaf si egdirb nodnoL”
上面這一串字娘摔，你可能根本看不懂窄坦，但是沒(méi)有關(guān)系。接下來(lái)我們?cè)偻瓿傻诙剑憔涂辞宄恕?/p>
第二步鸭津，把用空格分割的每一個(gè)字串以字母為單位彤侍，頭尾對(duì)調(diào)。比如第一個(gè)字串是nwod曙博，頭尾對(duì)調(diào)后是down拥刻，也就是原來(lái)句子中的最后一個(gè)單詞。第二個(gè)字串是gnillaf父泳，字母頭尾對(duì)調(diào)后是falling般哼，原來(lái)句子中倒數(shù)第二個(gè)單詞。這樣一個(gè)個(gè)地做惠窄，直到最后一個(gè)字串里的字母對(duì)調(diào)完畢蒸眠。這樣就得到了下面的倒裝句子：
“down falling is bridge London.”
這個(gè)問(wèn)題有兩個(gè)反思：
1. 遞歸可以簡(jiǎn)化問(wèn)題；
2. 有時(shí)候要打破常規(guī)思維杆融，為了達(dá)到目的楞卡，可能中間會(huì)有看似無(wú)意義的事情，但只要信息沒(méi)有丟失脾歇，看似無(wú)意義的事情還可以還原回有意義的事情蒋腮。
