Sort a string based on the order of another string

Question

I was tasked with ordering a string based on another string assuming everything in the string is also in the sorting string

E.G.

s = "Hello World"

orderString = " odlehwr"

output: " oodlllehwr"

I managed to do it in O(nlogn) time, but I was told after that it should be O(n + m) time and I just don't see how it's possible since it's a sort function, but I hope someone could point me in the right direction.

Here's my original code:

std::string _sortOrder;
std::string _input;

bool customComp(char c1, char c2) {
    //checks to see which is equal first in sequential order
    for (int i = 0; i < _sortOrder.length(); i++) {
        if (_sortOrder[i] == c2) {
            return false;
        }
        else if (_sortOrder[i] == c1) {
            return true;
        }
    }
}

void Question2::SortLetters(char* input, char* sortOrder) {
    //uses strings for maintainability
    _sortOrder = sortOrder;
    _input = input;

    //sorts using the custom comparator based on sortOrder
    std::sort(_input.begin(), _input.end(), customComp);
    std::copy(_input.begin(), _input.end(), input);
}

Your code is O(mnlogn), you can map the first string characters to int and use it to lower the time complexity. — ashkan_d13, Dec 16 '20 at 19:15

score 2 · Accepted Answer · answered Dec 16 '20 at 19:16

2

You actually don't need to do any sorting at all here. Since you know that you only have m unique characters, you can make m buckets (in code, this would probably look like a dictionary or a hash table). Then you just need to keep a count for each character.

After that, it's just a matter of looping through the sorted string and repeating each character however many times you saw it.

So the algorithm in pseudocode would look like:

string s = "Hello World";
string ordered = " odlehwr"
dictionary dict;
for (char c in s) {
    dict[c]++;
}

string sorted = "";
for (char c in ordered) {
    sorted += string(c, dict[c]); // repeat c, dict[c] times
}

answered Dec 16 '20 at 19:16

scohe001

15,110
2
31
51

There's no such thing as a `dictionary` in c++. You can use a `std::unordered_map`. – super Dec 16 '20 at 19:19
@super "*So the algorithm in pseudocode would look like.*" In my experience "dictionary" and "map" are interchangeable in the programming world (https://stackoverflow.com/q/2884068/2602718). And the `unordered_map` you recommend is a hash table. I'd rather avoid just giving OP a working solution. – scohe001 Dec 16 '20 at 19:24
Thanks! That makes sense, would have never thought of it that way. – Joshua20072 Dec 16 '20 at 19:44

Sort a string based on the order of another string

1 Answers1