Easy understanding C++ solution with detailed explnation


  • 9

    To solve this problem, we must keep in heart the following points:

    1. We know the cut point must come from the one string, assumed it is called c-string.
    2. Then except the c-string, all the other string must become its lexicographically biggest status, assumed it is called b-status. Since only in this situation, we could get the lexicographically biggest string after cutting.
    3. To reach the point 2, we need to first let all the string reach its b-status for the convenience of traversing all the strings afterward.
    4. Then, for each string's traversal procedure, we need to decide whether it should be reversed or not since we don't know which might generate the final answer, and then we enumerated all the characters in this string.
    class Solution {
    public:
        int n;
        string ans = "";
        // solve function: flag - whether we need to reverse the string; i - the ith string in the strs
        void solve(vector<string>& strs, int i, bool flag) {
            string temp = strs[i]; // intermediate string for not disturbing the original structure of 'strs'
            if (flag) reverse(temp.begin(), temp.end());
            int size = (int)temp.size();
            string str1 = "", str2 = "";
            for (int j=i+1; j<n; ++j) str1 += strs[j]; // Concatenate all the string behind the strs[i]
            for (int j=0; j<i; ++j) str2 += strs[j]; // Concatenate all the string before the strs[i]
            // traverse all the string character
            for (int k=0; k<size; ++k) {
                string newOne = temp.substr(k) + str1 + str2 + temp.substr(0, k); // cut and find the regular string
                ans = ans == "" ? newOne : max(ans, newOne); // update the ans
            }
        }
        // Reach the b-status for all the strings.
        void findMaxStrings(vector<string>& strs) {
            for (int i=0; i<n; ++i) {
                string temp = strs[i];
                reverse(temp.begin(), temp.end());
                strs[i] = strs[i] > temp ? strs[i] : temp;
            }
        }
        // Main function
        string splitLoopedString(vector<string>& strs) {
            n = (int)strs.size();
            if (n == 0) return "";
            findMaxStrings(strs);
            for (int i=0; i<n; ++i) {
                // we dont's know which will generate the final answer, so we traverse both situations.
                solve(strs, i, true); // reverse the string situation
                solve(strs, i, false); // not reverse the string situation
            }
            return ans;
        }
    };
    

  • 0
    V

    @love_Fawn similar idea, but shorter and faster (9 ms vs 100 ms): C++ 9ms 12 lines.


  • 2

    Thanks for your post, but actually we can move these two lines out of the loop, since for each iteration of k they are the same.

        for (int j=i+1; j<n; ++j) str1 += strs[j]; // Concatenate all the string behind the strs[i]
                for (int j=0; j<i; ++j) str2 += strs[j]; // Concatenate all the string before the strs[i]
    

    In fact, we even don't need to recompute the concatenated middle part every time. When we iterate the "cutting string", we just need delete the first string in the middle part and add one string to the last part as I did in my code.

        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;
        }
    

  • 0
    G

    @votrubac but your solution having more time complexity like O(n^2) compare to @love_Fawn solution


  • 0
    M

    @love_Fawn thanks for sharing. Changed the naming a little bit:

    class Solution {
    public:
        string splitLoopedString(vector<string>& strs) {
            n = strs.size();
            if(!n) return "";
            updateStrings(strs);
            for(int i = 0; i < n; ++i){
                solve(strs, i, true);
                solve(strs, i, false);
            }
            return res;
        }
        
    private:
        int n;
        string res;
        void updateStrings(vector<string>& strs){
            for(auto& str : strs){
                string tmp(str);
                reverse(tmp.begin(), tmp.end());
                str = tmp > str ? tmp : str;
            }
        }
        
        void solve(vector<string>& strs, int pos, bool isReversing){
            string tmp(strs[pos]);
            if(isReversing) reverse(tmp.begin(), tmp.end());
            
            int m = tmp.size();
            string s1 = "", s2 = "";
            for(int i = pos + 1; i < n; ++i) s1 += strs[i];
            for(int i = 0; i < pos; ++i) s2 += strs[i];
            
            for(int i = 0; i < m; ++i){
                string candidate = tmp.substr(i) + s1 + s2 + tmp.substr(0, i);
                res = res == ""? candidate : max(res, candidate);
            }
        }
    };
    

  • 0
    T

    whats the complexity of love_fown solution ?


Log in to reply
 

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