Java straight forward method with explanation


  • 3
    1. for each string other than the one we place the cut we choose the bigger one between itself and its reverse. We use the bigger one in the final concatenation.
    2. for the string which we cut - strs[i], we try each cut position for both strs[i] and its reverese, concatenate the other words after it to find the maximum result.
    3. we don't need to recaculate the concatenated string completely everytime. When we iterate through the cutting string we just need remove the first string and add last string to the mid part.
        public static String splitLoopedString(String[] strs) {
            int n = strs.length;
            for (int i = 0; i < n; i++) {
                String rev = new StringBuilder(strs[i]).reverse().toString();
                if (strs[i].compareTo(rev) < 0) strs[i] = rev;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n-1; i++) sb.append(strs[i]);
            String mid = sb.toString(), result = mid+strs[n-1];
            for (int i = 0; i < n; i++) {
                String str = strs[i], rev = new StringBuilder(str).reverse().toString();
                mid = mid.substring(str.length())+strs[(i+n-1)%n];
                for (int j = 0; j <= str.length(); j++) {
                    String s1 = str.substring(j)+mid+str.substring(0, j), s2 = rev.substring(j)+mid+rev.substring(0, j);
                    if (s1.compareTo(s2) >= 0 && s1.compareTo(result) > 0) result = s1;
                    else if (s2.compareTo(s1) >= 0 && s2.compareTo(result) > 0) result = s2;
                }
            }
            return result;
        }
    

Log in to reply
 

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