Cannot re-arrange string in Python

Question

I am trying to work through this Leetcode challenge. Basically, this is the problem:

I am given a string codeleet and list if integers [4,5,6,7,0,2,1,3] and I have to sort the indeces from 0 to n and thereby re-arranging the letters to get leetcode. This is my code. I am just appending every letter from s to output by making sure I am reaching the ith element of the letter corresponding to the indices:

class Solution:
    def restoreString(self, s: str, indices: List[int]) -> str:
        output = ''
        
        # append to output each character starting from index 0
        
        for i in range(0, len(indices)):
            output += s[indices[i]]
        print(output)

But this is the output of the test case:

leetcdoe

It rearranges most of it correctly but then it messes up. Why is this the case?

score 2 · Accepted Answer · answered Apr 19 '21 at 04:39

You are encoding the string, not decoding it. It is totally accidental that the first few letters are correctly in place. If you execute your code step by step using a pen and paper you'll see it.

Try this:

for i in sorted(indices):
    output += s[indices.index(i)]

score 1 · Answer 2 · answered Apr 19 '21 at 04:35

TL;DR

An overthinking solution...

def restore_str(s, indices):
    dictionary = dict(zip(indices, s))
    _, word = zip(*sorted(dictionary.items()))
    return ''.join(word)

First read the indices and characters in s, through a zip, see How to iterate through two lists in parallel?

Then cast the two list into a dict How do I convert two lists into a dictionary?

Then sort the dictionary since by the indices.

Finally read the 2nd element in each of each item returned from dictionary.items() using zip(*sorted(...))

Then join all the characters in the word, Convert a list of characters into a string

score 0 · Answer 3 · answered Apr 19 '21 at 04:40

The following will get the correct string

''.join(c for _, c in sorted(zip(indices, s))

Zipping the indices with the string and then sorting will give you a list of tuples where the second element of each tuple is the char in the correct position

Then you use ''.join to join together the second element of each tuple

Cannot re-arrange string in Python

3 Answers3

TL;DR