neat Java solution with brief explanation


  • 2
    T

    Updated: optimized by using a variable to maintain the lexicographically biggest character. Thanks to the idea from @shawngao. The running time now is about 60ms.

    Step 1: Compare every string with its own reverse, if the reverse is lexicographically bigger, then replace the string with reverse.
    Step 2: Concatenate all the strings into one, called 'stot'. Use 'maxch' to maintain the current biggest character.
    Step 3: Loop over every string and every character within the string. Each time you meet a character that is no smaller than 'maxch', update 'maxch', then build two candidate solutions s1, s2 based on 'stot'. (s1 and s2 starts at 'maxch' in two directions). Compare s1, s2 with the current best solution. Finally you get the best solution.

    '''

    public String splitLoopedString(String[] strs) {
        String stot = "";
        for (int i = 0; i < strs.length; i++) {
            String rever = new StringBuffer(strs[i]).reverse().toString();
            if (rever.compareTo(strs[i]) > 0) strs[i] = rever;
            stot = stot + strs[i];
        }
        int start = 0;
        String sol = stot;
        char maxch = 'a';
        for (int i = 0; i < strs.length; i++) {
            int n = strs[i].length();
            start += n;
            String rever = new StringBuffer(strs[i]).reverse().toString();
            String other_strs = stot.substring(start) + stot.substring(0, start - n);
            for (int j = 0; j < n; j++) {
                if (strs[i].charAt(j) - maxch >= 0) {
                    maxch = strs[i].charAt(j);
                    String s1 = strs[i].substring(j) + other_strs + strs[i].substring(0, j);
                    String s2 = rever.substring(n-1-j) + other_strs + rever.substring(0, n-1-j);
                    if (s1.compareTo(sol) > 0) sol = s1;
                    if (s2.compareTo(sol) > 0) sol = s2;
                }
            }
        }
        return sol;
    }
    

    '''

    It's true that you don't have to consider comparing the two strings which are both as long as solution. Ideally you may just need to consider comparing two strings both with length 2. But in the worst case you still have to.
    To save memory you have to write more lines. And in some cases like when a 'z' appear in the first or last position in a string, you need to write more 'if-else'.
    By the way, in java, substring() method is O(1). Thus my time complexity should be better than considering character by character.


  • 0

    @tchen31

    I have one question about your 3 steps.

    For example, ["lc", "evol", "cdy"].
    Step 1 => ["lc", "love", "ydc"]
    Step 2 => String stot = "lcloveydc"
    Step 3? No matter which break point you choose and which direction you go, you will not get the correct answer.


  • 1
    T

    @Nakanu Sorry I guess my explanation about s1 and s2 was kind of confusing. By saying "s1 and s2 starts at 'maxch' in two directions" I was trying to say considering the string containing 'maxch' in two direction.
    In your example, 'maxch' (which is y) is in string "ydc", then you consider starting from 'y', just inside "ydc", in two directions. One direction gives you "ydc"->"lc"->"love", the other direction gives you "y"->"lc"->"love"->"cd". The solution is the second one.


  • 0

    @tchen31
    Thank you for your clarification.


Log in to reply
 

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