CODEWITHSUNDEEP
pythonpython-3.x
user7594840
user7594840

Reputation: 103

For loop stores old variable value?

I am trying to implement ZigZag from LeetCode. Somehow during the second recursive call my second for loop within "addElements" retains the value from the last call. Why does this happen?

I have shared the output below - my question is in regards to how beg and end stay the same value until 3, then beg moves to 6 as expected but end remains at 3.

https://leetcode.com/problems/zigzag-conversion/ 

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        row = [''] * len(s)
        self.s = s
        self.numRows = numRows
        self.final_grid = []

        for i in range(numRows):
            self.final_grid.append(list(row))

        self.addElements(0, 0)

        final_arr = []
        for i in self.final_grid:
            final_arr += i

        final_word = ''
        for i in final_arr:
            if i != "":
                final_word += i

        return (final_word)



    def addElements(self, count, column):
        print(column, "beg")
        for i in range(self.numRows):
            if count > len(self.s) - 1:
                break
            self.final_grid[i][column] = self.s[count]
            count += 1

        for i in range(1, self.numRows - 1):
            if count > len(self.s) - 1:
                break

            self.final_grid[self.numRows - i - 1][column + i] = self.s[count]
            count += 1
            print(column, "end")
            self.addElements(count, column + self.numRows - 1)

INPUT: "PAYPALISHIRING" 4

STDOUT:
0 beg
0 end
3 beg
3 end
6 beg
3 end **why does this stay at 3?
6 beg
0 end 
3 beg
3 end
6 beg
3 end
6 beg

Output: "PINALSIGYAHRGPIG"

Expected: "PINALSIGYAHRPI"

Upvotes: 1

Views: 109

Answers (2)

ggorlen
ggorlen

Reputation: 56865

The problem appears to be this block:

    for i in range(1, self.numRows - 1):
        if count > len(self.s) - 1:
            break

        self.final_grid[self.numRows - i - 1][column + i] = self.s[count]
        count += 1
        print(column, "end")
        self.addElements(count, column + self.numRows - 1)

Here, you are recursing for every element in the loop. You probably meant:

def addElements(self, count, column):
    for i in range(self.numRows):
        if count >= len(self.s):
            return # <-- return instead of break

        self.final_grid[i][column] = self.s[count]
        count += 1

    for i in range(1, self.numRows - 1):
        if count >= len(self.s):
            return # <-- return instead of break

        self.final_grid[self.numRows-i-1][column+i] = self.s[count]
        count += 1

    self.addElements(count, column + self.numRows - 1)
    #^^^ move this outside of the loop

With these changes, the output matches expected: "PINALSIGYAHRPI". The code is still a bit awkward and the various conditionals are strangely placed, doing double duty as pre/post conditions, so I'd consider a re-write.

Caveat: I've only taken a look at this problem and I'm not vouching that this code will work on the remainder of the tests. For one, it uses a huge amount of memory, so there is likely a way to build the result without creating a giant n x m array. There are other minor inefficiencies, like building the result array character by character, then building the result string from the array (runs in quadratic time because strings are immutable).

Instead of:

    final_arr = []
    for i in self.final_grid:
        final_arr += i

    final_word = ''
    for i in final_arr:
        if i != "":
            final_word += i

    return (final_word)

use:

    return "".join(map("".join, self.final_grid))

Instead of:

    row = [''] * len(s)

consider:

    row = [''] * ((len(s) // 2) + 1)

Upvotes: 1

PMM
PMM

Reputation: 376

Because the last element of the for loop stores the last variable. To make so that you don't have that variable type del variable if you try to use that variable without reassigning a new value, it will throw an error

Upvotes: 0

Related Questions