[LeetCode] Split Concatenated Strings 分割串聯字元串

Given a list of strings, you could concatenate these strings together into a loop, where for each string you could choose to reverse it or not. Among all the possible loops, you need to find the lexicographically biggest string after cutting the loop, which will make the looped string into a regular one.

Specifically, to find the lexicographically biggest string, you need to experience two phases:

Concatenate all the strings into a loop, where you can reverse some strings or not and connect them in the same order as given.

Cut and make one breakpoint in any place of the loop, which will make the looped string into a regular one starting from the character at the cutpoint.

And your job is to find the lexicographically biggest one among all the possible regular strings.

Example:

Note:

The input strings will only contain lowercase letters.

The total length of all the strings will not over 1,000. 

這道題給了我們一些字元串，讓我們将其連接配接起來，連接配接的時候對于每個字元串我們可以選擇翻轉或者不翻轉，在行程的大的字元串上找一個位置cut掉，将該位置當作首字元，前面的字元串移動到末尾去，問怎麼cut能使字元串的字母順序大。剛開始部落客想，既然要讓最終字元串字母順序最大，那麼每一個字元串當然要盡可能的大了，是以如果其翻轉字元串的字母順序大的話，就要對字元串進行翻轉。然後在組成的字元串中找最大的字元進行cut，然而這種思路不一定能得到正确的結果。比如字元串數組["lc", "love", "ydc"]，如果按照部落客之前的思路得到的字元串應該為"ydclclove"，但正确結果應該是"ylclovecd"。我們可出來正确的答案中cut位置所在的字元串ydc，雖然cdy小于ydc，但還是翻轉了。但是其他的字元都是按照字母順序來确定要不要翻轉的，那麼我們可以得出這樣的結論，隻有cut所在的字元串的翻轉可能不按規律。那麼我們如何确定cut位置呢，其實沒有太好的辦法，隻能周遊每一個字母。我們首先來根據字母順序确定要不要翻轉每一個字元串，将字母順序大的連成一個字元串，然後周遊每一個字元串，在每一個字元串中周遊每一個位置，将目前周遊的字元串後面的所有字元串跟前面所有字元串先連起來，存入mid中，然後取出目前周遊的字元串中目前周遊的位置及其後面的字元取出，連上mid，然後再連上目前位置前面的字元，然後跟結果res比較，取較大者存入結果res。這裡我們可以進行小優化，如果cut位置的字母大于等于結果res的首字母，我們才進行對比更新。注意我們在周遊每個字元串時，要将其翻轉字元串的每一位也周遊了，這樣才能涵蓋所有的情況，參見代碼如下：

<a>class Solution {</a>

參考資料：

<a href="https://discuss.leetcode.com/topic/86545/c-9ms-12-lines/2" target="_blank">https://discuss.leetcode.com/topic/86545/c-9ms-12-lines/2</a>

<a href="https://discuss.leetcode.com/topic/86509/easy-understanding-c-solution-with-detailed-explnation" target="_blank">https://discuss.leetcode.com/topic/86509/easy-understanding-c-solution-with-detailed-explnation</a>

，如需轉載請自行聯系原部落客。