Split Concatenated Strings (Leetcode 555)

Alibaba的题，这道题我参照了下面的解法，非常巧妙.

https://discuss.leetcode.com/topic/87446/java-straight-forward-method-with-explanation

第一步，我们update原string array，如果strs[i].reverse > strs[i], 则strs[i] = strs[i].reverse. 这步是需要的，在做第二步时，可以确保mid string是最优的

第二步，对于一个string array，比如 "abc", "def", "xyz", 我们先生成一个mid string，mid string没有最后一个string，比如"abcdef". 然后我们update mid string:

mid = mid.substr(str.length()) + strs[(i+n-1) % n];

这样mid string就变成 defxyz(由abcdef，去掉abc，加上xyz)，xyzabc.

然后我们扫原string array中的每一个string，生成相应的截取result。比如对于abc，我们有mid string = defxyz, 所以组合是：
正序：abc-defxyz, bc-defxyz-a, c-defxyz-ab, defxyz-abc
反序：cba-defxyz, ba-defxyz-c, a-defxyz-cb, defxyz-cba,
然后我们所有循环中挑出全局最大的.

class Solution {
public:
    string splitLoopedString(vector<string>& strs) {
        if(strs.empty()) return "";
        else if(strs.size() == 1) return max(strs[0], string(strs[0].rbegin(), strs[0].rend()));
        string all = "";
        int n = strs.size();
        for(int i=0; i<n; i++){
            string temp = string(strs[i].rbegin(), strs[i].rend());
            if(temp > strs[i]) strs[i] = temp;
        }
        for(int i=0; i<n-1; i++){
            all += strs[i];
        }
        string result = all + strs[n-1];
        for(int i=0; i<n; i++){
            string str = strs[i], rev = string(strs[i].rbegin(), strs[i].rend());
            all = all.substr(str.length()) + strs[(i+n-1) % n];
            for(int j=0; j<=str.length(); j++){
                string s1 = str.substr(j) + all + str.substr(0, j), s2 = rev.substr(j) + all + rev.substr(0, j);
                if(s1 >= s2 && s1 > result) result = s1;
                else if(s2 >= s1 && s2 > result) result = s2;
            }
        }
        return result;
    }
};