LeetCode-Solutions/C++/shuffle-string.cpp at master · usman3721/LeetCode-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Time:  O(n)
// Space: O(1)

// in-place solution
class Solution {
public:
    string restoreString(string s, vector<int>& indices) {
        for (int i = 0; i < s.length(); ++i) {
            if (indices[i] == i) {
                continue;
            }
            auto move = s[i];
            for (int j = indices[i]; j != i; swap(indices[j], j)) {
                swap(s[j], move);
            }
            s[i] = move;
        }
        return s;
    }
};

// Time:  O(n)
// Space: O(1)
class Solution2 {
public:
    string restoreString(string s, vector<int>& indices) {
        string result(s.length(), 0);
        for (int i = 0; i < s.length(); ++i) {
            result[indices[i]] = s[i];
        }
        return result;
    }
};