題目連結:
題目大意:
輸入有多筆測試資料,每筆佔兩列(只有一列「#」時,代表輸入結束)。測資兩列各自給定兩個字串(長度最多 100 字元,可能會有空白字元),代表父親推薦的旅程順序以及母親推薦的旅程順序(每個字元代表一個地點)。
試問在不違反父親以及母親各自的建議順序(只要地點相對順序都符合兩者,就沒有違反),最多可以去幾個地點旅行?輸出格式參見範例輸出。
範例輸入:
abcd
acdb
abcd
dacb
abcd
dcba
#
範例輸出:
Case #1: you can visit at most 3 cities.
Case #2: you can visit at most 2 cities.
Case #3: you can visit at most 1 cities.
解題思維:
雖然題目講得很隱諱,但是仔細觀察就可以看到這題其實就是求兩個字串的最長共同子序列(Longest Common Subsequence,LCS)。作法可以參見
這題。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。