题目描述：

LeetCode 555. Split Assembled Strings

Given a list of strings, you could assemble these strings together into a loop. Among all the possible loops, you need to find the lexicographically biggest string after cutting and making one breakpoint of the loop, which will make a looped string into a regular one.

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

1. Assemble all the strings into a loop, where you can reverse some strings or not and connect them in the same order as given.
2. Cut and make one breakpoint in any place of the loop, which will make a looped string into a regular string starting from the character at the cutting point.

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

Example:

Input: "abc", "xyz"
Output: "zyxcba"
Explanation: You can get the looped string "-abcxyz-", "-abczyx-", "-cbaxyz-", "-cbazyx-", 
where '-' represents the looped status. 
The answer string came from the third looped one, 
where you could cut from the middle and get "zyxcba".

Note:

1. The input strings will only contain lowercase letters.
2. The total length of all the strings will not over 1000.

题目大意：

给定一组字符串，其中每个字符串可以逆置，将字符串按照原始顺序拼接组成一个环，从中选择一个位置切开。

求得到的字符串中字典序最大的字符串。

注意：

1. 输入字符串只包含小写字母
2. 字符串总长度不超过1000

解题思路：

字符串处理

遍历strs中的字符串，若逆置后的字典序较大，则将其逆置

枚举字符串st，记下标为i，st左右两侧的字符串分别为left, right

在st中枚举起点j，则s[j:] + right + left + s[:j]为环形字符串从j处切割得到的新字符串

需要注意的是在枚举st时，需要同时判断st与st的逆置

Python代码：

class Solution(object):
    def splitLoopedString(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        strs = [max(s, s[::-1]) for s in strs]
        ans = ''
        for i, st in enumerate(strs):
            left, right = ''.join(strs[:i]), ''.join(strs[i+1:])
            for s in (st, st[::-1]):
                for j in range(len(s)):
                    ans = max(ans, s[j:] + right + left + s[:j])
        return ans

 

本文链接：http://bookshadow.com/weblog/2017/04/16/leetcode-split-assembled-strings/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码