LeetCode 1528. Shuffle String

September 13, 2020

The problem statement limits the inputs a lot, so we don't need to do much, if any, error checking.

An $O(n)$ algorithm could look like:

Create a list, $restored$ , of length $n$ .
For each integer, $i$ , in $indices$ , set $restored[i]$ = $s[i]$ .
Return $restored$ as a string.

We can't do better than $O(n)$ since we must touch each element in $s$ at least once if we're to unshuffle it.

from typing import List
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.restoreString("codeleet", [4,5,6,7,0,2,1,3]), "leetcode")
        self.assertEqual(self.s.restoreString("abc", [0,1,2]), "abc")
        self.assertEqual(self.s.restoreString("aiohn", [3,1,4,2,0]), "nihao")
        self.assertEqual(self.s.restoreString("aaiougrt", [4,0,2,6,7,3,1,5]), "arigatou")
        self.assertEqual(self.s.restoreString("art", [1,0,2]), "rat")

    def test_empty(self):
        self.assertEqual(self.s.restoreString("", []), "")

class Solution:

    def restoreString(self, s: str, indices: List[int]) -> str:
        restored = [""] * len(s)
        for i in indices:
            restored[indices[i]] = s[i]
        return "".join(restored)

if __name__ == "__main__":
    unittest.main()