10739 - String to Palindrome

本問題請你轉換一字串使之變成迴文字串(一種從前面寫與從後面寫都一樣的字串，例如abcba)，藉由新增、刪除、取代字母等步驟來轉換成迴文字串，並使轉換的步驟最小化。更精確地說，你可以執行的步驟有三種：

• 新增：插入一字母到字串中任一位置。
• 刪除：刪除字串中任一字母。
• 取代：以一個字母取代字串中任一字母。

每執行上述三種步驟中的任一種即算一次，你必需使轉換步驟愈少愈好。

例如字串"abccda"，如果只允許以新增字母的方式轉換字串，則最少需要兩個步驟，若允許以取代的方式轉換字串，則最少僅需一個步驟。當然，本問題是允許你三種步驟都能使用。

Input

輸入的第一列有一個整數T(1 <= T <= 10)表示接下來有T列測試資料，每列測試資料皆為一個僅含小寫字母的字串，字串長度不會超過1000個字元。

Output

請對每組測試資料輸出其編號，與使字串變成迴文字串的最少步驟為何。

Sample Input                               Output for Sample Input

6 tanbirahmed shahriarmanzoor monirulhasan syedmonowarhossain sadrulhabibchowdhury mohammadsajjadhossain

Case 1: 5 Case 2: 7 Case 3: 6 Case 4: 8 Case 5: 8 Case 6: 8

---

原文出處