C++ 9ms 12 lines


  • 7
    V

    The idea is similar to this post by @love_FDU_llp; just optimized for brevity and performance (9 ms vs. 100 ms).
    Optimization 1: do not check the cutting point if the first letter is smaller than the first letter of the current best result.
    [Removed as producing incorrect results] Optimization 2: if a sub-string best result is the same as the current best result, then there is a lop and we are done.
    I also tried few more ideas, but it did not improve OJ runtime but increased the number of lines.

    string splitLoopedString(vector<string>& strs) {
        string s = "", res = "a";
        for (auto i = 0; i < strs.size(); ++i) {
            auto r = strs[i];
            reverse(r.begin(), r.end());
            s += max(r, strs[i]);
        }
        for (auto i = 0, st = 0; i < strs.size(); st += strs[i++].size()) {
            auto p1 = strs[i], p2 = strs[i], body = s.substr(st + p1.size()) + s.substr(0, st);
            reverse(p2.begin(), p2.end());
            for (auto j = 0; j < strs[i].size(); ++j) {
                if (p1[j] >= res[0]) res = max(res, p1.substr(j) + body + p1.substr(0, j));
                if (p2[j] >= res[0]) res = max(res, p2.substr(j) + body + p2.substr(0, j));
            }
        }
        return res;
    }
    

  • 2

    It's wrong, fails for example input ["b", "z", "a", "bza"]. You return "zabzab", correct is "zbbzaa".


  • 0
    V

    @StefanPochmann said in C++ 6ms 14 lines:

    ["b", "z", "a", "bza"]

    Thanks Stefan, I was thinking about that test case as well. I have updated the code; the exit condition should be checked after the entire sub-string is processed.


  • 0

    @votrubac So now try ["b", "z", "a", "b", "z", "a", "bza"] :-). You return "zabzabzab" instead of "zbbzabzaa".


  • 0
    V

    @StefanPochmann I know, I know... I removed this optimization. I think that the solution is still good enough - the code is shorter and runtime is 9 ms. My original intent was to optimize for cases like ["ab", "cd", "ab", "cd" ..., "ab", "cd"]. I guess that there is no easy way to do it.


  • 0

    @votrubac Maybe try to find such repetitions first. In the vector of strings. For example, using @rsrs3's solution for the Repeated Substring Pattern problem:

    auto twice = strs;
    twice.insert(twice.end(), strs.begin(), strs.end());
    int k = search(twice.begin() + 1, twice.end(), strs.begin(), strs.end()) - twice.begin();
    

    And then using for (...; i < k; ...) as your loop.


  • 0
    G

    @StefanPochmann said in C++ 9ms 12 lines:

    bza
    for input ["b", "z", "a", "b", "z", "a", "bza"] you say output is "zbbzabzaa"

    Could you please explain the problem. i am confused with this output. i thought problem is we need to combine all string's (we can do reverse/rotation of each string) so that resultant string is lexicographically sorted.

    could you please explain this problem what its asking.


Log in to reply
 

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