555. 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:

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 fourth looped one,
where you could cut from the middle character ‘a’ and get “zyxcba”.

Note:

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

解法1：O(N^2)　

此题参考了leetcode的解法：

order to understand how this solution works, firstly we'll look at some of the properties of the transformation involved. The first point to note is that the relative ordering of the strings doesn't change after applying the transformations(i.e. reversing and applying cuts).
1
2
3
4
5
6
7
8
9
10
The second property will be explained taking the help of an example. Consider the given list of strings: [s1,s2,s3,..,sj,..sn][s_1, s_2, s_3,..,s_j,..s_n][s​1​​,s​2​​,s​3​​,..,s​j​​,..s​n​​]. Now, assume that we choose sjs_js​j​​ to be the string on which the current cut is placed leading to the formation of two substrings from sjs_js​j​​, namely, say sjpres_{jpre}s​jpre​​, sjposts_{jpost}s​jpost​​. Thus, the concatenated string formed by such a cut will be: [sjpost,sj+1,...,sn,s1rev,s2rev,..,s(jpre)rev][s_{jpost}, s_{j+1},..., s_n, s_{1rev}, s_{2rev},.., s_{(jpre)rev}][s​jpost​​,s​j+1​​,...,s​n​​,s​1rev​​,s​2rev​​,..,s​(jpre)rev​​]. Here, sirevs_{irev}s​irev​​ means the reversed sis_is​i​​ string.
The concatenated string formed follows the same pattern irrespective of where the cut is placed in sjs_js​j​​. But still, the relative ordering of the strings persists, even if we include the reverse operation as well.
Now, if we consider only a single cut for the time being, in string sjs_js​j​​(not reversed) as discussed above, and allow for the reverse operation among the remaining strings, the lexicographically largest concatenated string will be given by: [sjpost,max(sj+1,s(j+1)rev),...,max(sn,s(n)rev),max(s1,s(1)rev),...,s(jpre)rev][s_{jpost}, \text{max}(s_{j+1},s_{(j+1)rev}) ,..., \text{max}(s_{n},s_{(n)rev}), \text{max}(s_{1},s_{(1)rev}), ..., s_{(jpre)rev}][s​jpost​​,max(s​j+1​​,s​(j+1)rev​​),...,max(s​n​​,s​(n)rev​​),max(s​1​​,s​(1)rev​​),...,s​(jpre)rev​​]. Here, max\text{max}max refers to the lexicographic maximum operation.
Thus, if a particular string sjs_js​j​​ is finalized for the cut, the largest lexicographic concatenated string is dependent only on whether the string sjs_js​j​​ is reversed or not, and also on the position of the cut. This happens because the reverse/not reverse operation for the rest of the strings is fixed for a chosen sjs_js​j​​ as shown above and thus, doesn't impact the final result.
Based on the above observations, we follow the given procedure. For every given string, we replace the string with the lexicographically larger string out of the original string and the reversed one. After this, we pick up every new string(chosen as the string on which the cuts will be applied), and apply a cut at all the positions of the currently picked string and form the full concantenated string keeping the rest of the newly formed strings intact. We also reverse the current string and follow the same process. While doing this, we keep a track of the largest lexicographic string found so far.

C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solution {
    public String splitLoopedString(String[] strs) {
        for (int i = 0; i < strs.length; i++) {
            String rev = new StringBuilder(strs[i]).reverse().toString();
            if (strs[i].compareTo(rev) < 0) {
                strs[i] = rev;
            }
        }
        String res = "";    // store results
        for (int i = 0; i < strs.length; i++) {
            String rev = new StringBuilder(strs[i]).reverse().toString();
            for (String str : new String[] {strs[i], rev}) {
                for (int k = 0; k < str.length(); k++) {
                    // get the head
                    StringBuilder builder = new StringBuilder(str.substring(k));
                    // append i + 1 to n strings
                    for (int j = i + 1; j < strs.length; j++) {
                        builder.append(strs[j]);
                    }
                    // append 0 to i -1 strings
                    for (int j = 0; j < i; j++) {
                        builder.append(strs[j]);
                    }
                    builder.append(str.substring(0, k));
                    if (builder.toString().compareTo(res) > 0) {
                        // lexi order
                        res = builder.toString();
                    }
                }
            }
        }
        return res;
    }
}