CODEWITHSUNDEEP
pythonalgorithm
mchd
mchd

Reputation: 3163

Cannot re-arrange string in Python

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

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?

Upvotes: 1

Views: 70

Answers (3)

Iain Shelvington
Iain Shelvington

Reputation: 32294

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

Upvotes: 0

Selcuk
Selcuk

Reputation: 59425

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

Upvotes: 2

alvas
alvas

Reputation: 122240

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

Upvotes: 1

Related Questions