筆試算法模拟題精解之“Jerry的考驗”

【線上程式設計産品介紹】

阿裡雲開發者社群線上程式設計：

免費刷題大神器，助你拿到好offer

周賽月賽不停歇，做題還能領獎品

大賽筆試全真題，常做常新有驚喜

點選連結開始産品體驗：

https://developer.aliyun.com/coding 本文為大家介紹的是“106.Jerry的考驗”的解法探究。先來看一下題目内容：

題目詳情

等級：中等

知識點：搜尋、字元串、位運算

檢視題目：Jerry的考驗

有一天Jerry給Tom出了一道題來考驗他。Jerry給了Tom一個長度為2

*

n的隻包含小寫字母的字元串，讓Tom将這個字元串任意挑選字元，将其分成兩個等長的字元串a和b(對于一個si不能同時被選到a和b中)，然後a要和reverse(b)相同(a和反轉後的b相同)，問這樣的方案數有多少？Tom有些為難，是以請你來幫幫他吧。

輸入一個正整數n，和一個長度為2*n的字元串

輸出方案數。

示例1

輸入：

2

"abba"

輸出：

4

解題思路描述

本題的關鍵在于了解題意：所謂挑選n個字元變成a和b兩個字元串，是指在原字元串中抽出n個字元，這些字元的的順序保持不變，剩下字元的順序也保持不變，由此組成a和b兩個字元串。

例如 "abcdef"，挑選第2、3、5個字元，則分成 "bce" 和 "adf" 兩個串。

接下來是整理的思路解析：整體架構是dfs，枚舉每個字元屬于a還是屬于b，搜尋過程中需要利用a和b的對稱性做加速處理，否則會逾時。

比方說

xcccddcccxdd

從左往右枚舉a字元串的構成，如果令第一個x屬于a，根據對稱性，倒數第三個字元x一定是屬于b；如此推導出末尾的dd一定屬于a，中間位置的dd一定屬于b，而且是b的頭兩個字元；然後左邊ccc一定a，右邊ccc一定是b，由此得出1種方案。令第一個x屬于b也可以用同樣的方式得到1種方案。

用這個思路直接寫代碼不太好寫，可以通過枚舉二進制，固定左半邊的選擇情況，然後對于每一個case，通過dfs搜尋右半邊有多少種合法組合，搜尋過程中利用對稱性進行剪枝。

對于字元全部相同case如"aaaaaaaa"，因為過程中無法剪枝，會退化成2^(2*n)。對于這種case，答案就是 C(2n,n) ，預判一下直接傳回即可。

看完之後是不是有了答題思路了呢，快來練練手吧：

106.Jerry的考驗

線上程式設計周賽、月賽火熱進行中，更有限時答題活動，社群定制衛衣、雙肩背包等你來拿~每周都有好禮相送~點選了解周賽詳情：

線上程式設計3月份比賽正式開啟！機械鍵盤等你拿！