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?

Selcuk · Accepted Answer · 2021-04-19 04:39:54Z

2

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)]

answered Apr 19, 2021 at 4:39

Selcuk

60.1k12 gold badges114 silver badges119 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

alvas · Accepted Answer · 2021-04-19 04:35:53Z

1

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

answered Apr 19, 2021 at 4:35

alvas

123k118 gold badges503 silver badges807 bronze badges

Comments

Iain Shelvington · Accepted Answer · 2021-04-19 04:40:39Z

0

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

answered Apr 19, 2021 at 4:40

Iain Shelvington

32.5k3 gold badges36 silver badges55 bronze badges

Collectives™ on Stack Overflow

Cannot re-arrange string in Python

3 Answers 3

Comments

TL;DR

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

TL;DR

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related