Python, Straightforward with Explanation


  • 7

    For every starting direction and letter, let's determine the best string we can make. For subsequent fragments we encounter, we always want them flipped in the orientation that makes them largest.

    Thus, for every token, for every starting direction, for every starting letter in the token, we can compute the candidate string directly. We take the maximum of these.

    def splitLoopedString(self, A):
        B = [max(x, x[::-1]) for x in A]
        ans = None
        for i, token in enumerate(B):
            for start in (token, token[::-1]):
                for j in xrange(len(start) + 1):
                    ans = max(ans, start[j:] + "".join(B[i+1:] + B[:i]) + start[:j])
        return ans
    

  • 1
    Z
    This post is deleted!

  • 0
    C
    This post is deleted!

  • 0
    C

    thank you for very good explanation


  • 3

    Got almost the same, but written differently.

    def splitLoopedString(self, strs):
        strs = [max(s, s[::-1]) for s in strs]
        return max(s[j:] + ''.join(strs[i+1:] + strs[:i]) + s[:j]
                   for i, s in enumerate(strs)
                   for s in (s, s[::-1])
                   for j in xrange(len(s)))
    

    The one "real" difference is that I don't do the + 1 in the range for j. I don't think it's necessary or even meaningful, as in that case your start really isn't the start but only the end.


  • 0
    Z

    My java version, gotta appreciate Python's Simplicity :-(

    public class Solution {
        public String splitLoopedString(String[] strs) {
            int n = strs.length;
            List<String> lst = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                String s = strs[i];
                String reversed = new StringBuilder(s).reverse().toString();
                lst.add((s.compareTo(reversed) > 0) ? s : reversed);
            }
            String res = ""; 
            for (int i = 0; i < n; i++) {
                String[] temp = new String[] {strs[i], new StringBuilder(strs[i]).reverse().toString()};
                for (String start : temp) {
                    for (int j = 0; j < start.length(); j++) {
                        StringBuilder loop = new StringBuilder();
                        loop.append(start.substring(j));
                        // join
                        for (int k = 0; k < n - 1; k++) {
                            loop.append(lst.get((i + 1 + k) % n));
                        }
                        loop.append(start.substring(0, j));
                        res = (res.compareTo(loop.toString()) > 0) ? res : loop.toString();
                    }
                }
            }
            
            return res;
        }
        
        
    }
    
    

  • 0
    N

    my c# solution,

    public class Solution {
            public string SplitLoopedString(string[] strs)
            {
                var res = string.Empty;
                for (var i = 0; i < strs.Length; i++)
                {
                    var s = Reverse(strs[i]);
                    if (s.CompareTo(strs[i]) > 0)
                    {
                        strs[i] = s;
                    }
                }
    
                for (var i = 0; i < strs.Length; i++)
                {
                    var s = strs[i];
                    var other = string.Join(string.Empty, strs.Skip(i + 1).Take(strs.Length - i - 1)) + string.Join(string.Empty, strs.Take(i));
                    var tokens = new string[] { s, Reverse(s) };
                    foreach (var a in tokens)
                    {
                        for (var j = 0; j <= a.Length; j++)
                        {
                            var temp = string.Format("{0}{1}{2}", a.Substring(j), other, a.Substring(0,j));
                            if (temp.CompareTo(res) > 0)
                            {
                                res = temp;
                            }
                        }
                    }
                }
                return res;
            }
            public string Reverse(string s)
            {
                return new string(s.Reverse().ToArray());
            }
    }
    

  • 0
    L

    @StefanPochmann it doesn't say that the inputs are given lexicographically . So why do you choose to join(strs[i+1:]+strs[:i]) instead of join(strs[:i]+strs[i+1:])

    Ex: ["bab","xy","ba"]
    your answer would give "yxbabab", when the correct answer should be "yxbabba"


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.