Category: LeetCode

Question 91 Decode Ways

Question:

https://leetcode.com/problems/decode-ways/

 

My code

class Solution:
    def numDecodings(self, s: str) -> int:
# First we finish the part that the length of the string is 1
        if len(s) ==1:
            if int(s[0])== 0:
                return 0
            else:
                return 1
        else: # we then finish the part which has length larger than 1
            if int(s[0]) == 0:
                Mat = [0]*len(s)
            else:
                Mat = [1]*len(s)
            for StringNum in range(1,len(s)):
                if int(s[StringNum-1]) == 0:
                    if int(s[StringNum]) == 0:
                        Mat[StringNum] = 0
                    else:
                        if StringNum ==1:
                            Mat[StringNum]= 0
                        else:
                            Mat[StringNum] = Mat[StringNum-1] 
                elif int(s[StringNum-1])==1:
                    if int(s[StringNum])==0:
                        if StringNum == 1:
                            Mat[StringNum] = 1
                        else:
                            Mat[StringNum] = Mat[StringNum-2]
                    else:
                        if StringNum ==1:
                            Mat[StringNum] = 2
                        else:
                            Mat[StringNum] = Mat[StringNum-1]+Mat[StringNum-2]
                elif int(s[StringNum-1]) ==2:
                    if int(s[StringNum]) == 0:
                        if StringNum ==1:
                            Mat[StringNum] = 1
                        else:
                            Mat[StringNum] = Mat[StringNum-2]
                    elif int(s[StringNum]) >=7:
                        if StringNum ==1:
                            Mat[StringNum] =1
                        else:
                            Mat[StringNum] = Mat[StringNum-1]
                    else:
                        if StringNum ==1:
                            Mat[StringNum] = 2
                        else:
                            Mat[StringNum] = Mat[StringNum-1]+ Mat[StringNum-2]
                else:
                    if int(s[StringNum]) == 0:
                        Mat[StringNum] = 0
                    else:
                        if StringNum == 1:
                            Mat[StringNum] = 1
                        else:
                            Mat[StringNum] = Mat[StringNum-1]
        
        return Mat[len(s)-1]

Explanation:

The Structure of the code is a little difficult to explain in words. There will be (If I do not forget) a full chart to illustrate the whole idea.

Question 70 Climbing Stairs

The description of the question is in the following link:

https://leetcode.com/problems/climbing-stairs/

My Code:

class Solution:
    def climbStairs(self, n: int) -> int:
        Ladder = [1]*n;
        if n ==1: 
            return 1;
        else:
            Ladder[1] = 2;
            for LadNum in range(2,n):
                Ladder[LadNum] = Ladder[LadNum-1]+Ladder[LadNum -2]
            return Ladder[n-1]

Explanation:

The idea is clear: the only way to reach the nth ladder is that going from n-1th ladder with 1 step and n-2th ladder with 2 steps. So we just need to sum the number of steps to reach these two ladders to get the step to reach nth ladder. Just need to be very careful about some special situation and initialisation.

 

Question 64 minimum sum path

The description of the question is included in the following link:

https://leetcode.com/problems/minimum-path-sum/

My Code

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        RowNum = len(grid);
        ColNum = len(grid[0]);
        Mat = [[0]*ColNum for _ in range(RowNum)];
        Mat[0][0] = grid[0][0];
        for row in range(RowNum):
            if row == 0:
                for col in range(1,ColNum):
                    Mat[row][col] = grid[row][col]+ Mat[row][col-1];
            else:
                for col in range(ColNum):
                    if col ==0 :
                        Mat[row][col] = grid[row][col]+Mat[row-1][col];
                    else:
                        Mat[row][col] = min(Mat[row][col-1],Mat[row-1][col])+ grid[row][col];
        return Mat[RowNum-1][ColNum-1];

Explanation:

The idea behind the code is really simple. For each block, there are two ways to go in: from the top or from left block. We then just need to find the minimum value between these two then add the number in the block to have the minimum value that can go to that block. So we keep this procedure and then we may find the minimum value of the block we want.

Question 63 Unique Paths 2

The description of the question is in the following link:

https://leetcode.com/problems/unique-paths-ii/

My code:

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        Mat = [[1]*len(obstacleGrid[0]) for _ in range(len(obstacleGrid))];
        
        for row in range(len(obstacleGrid)):
            if row == 0 :
                for col in range(len(obstacleGrid[0])):

                        if obstacleGrid[row][col] ==1:
                            Mat[row][col] =0;
                        else:
                            Mat[row][col] = Mat[row][col-1];

            else:
                for col in range(len(obstacleGrid[0])):
                    if col == 0:
                        if obstacleGrid[row][col] == 1:
                            Mat[row][col] = 0;
                        else:
                            Mat[row][col] = Mat[row-1][col];
                    else:
                        if obstacleGrid[row][col] == 1:
                            Mat[row][col] = 0;
                        else:
                            Mat[row][col] = Mat[row][col-1]+Mat[row-1][col];
        return Mat[len(obstacleGrid)-1][len(obstacleGrid[0])-1];

Explanation: This part of the code is very similar to the previous part. Except that we need to be very careful about the situation that whenever there is a rock, we need to set the path number at that part as 0. I start from row 0 because there might be an obstacle on the row 0 or col 0, so we need to take this into consideration.

Question 62 Unique Path

The description of the question is in the following link:

My Code:

    def uniquePaths(self, m: int, n: int) -> int:
        Mat = [[1] * n for _ in range(m)]

        for col in range(1, m):
            for row in range(1, n):
                Mat[col][row] = Mat[col - 1][row] + Mat[col][row - 1];

        return d[m - 1][n - 1];

Explain: Starting From the very beginning and go one by one. Each step is generated from the sum of the step number above it and left to it.

 

Question 8 String to Integer

The description of the question is in the following link:

https://leetcode.com/problems/string-to-integer-atoi/

My Code:

    def myAtoi(self, String) -> int:
        if(String == ""):
            return(0);
        else:
            while(String[0] == " "):
                String = String[1:len(String)];
                if(String == ""):
                    return(0);
            sign = 1;
            if(String[0] == "-"):
                sign = -1;
                String = String[1:len(String)];
            else:
                if(String[0] == "+"):
                    String = String[1:len(String)];
            Number = ""
            i = 0;
            while(i 2**31-1):
                    return(2**31-1);
                else:
                    if(Number < -2**31):
                        return(-2**31);
                    else: 
                        return(Number);

Explanation:

The idea is clear. First part is to discard all the possible space. What we need to be very careful is the empty string. The second part is to determine if there is any potential sign for the number. The last part is to take all the available number string and then do the conversion.

Question 7 Reverse Integer

The description of the code is included in the following link.

class Solution:
    def reverse(self, x: int) -> int:
        if(x>=0):
            z = int(str(x)[::-1]);
            if (z>(2**31-1) ):
                return(0);
            else:
                return(z);
                
        else:
            z = abs(x);
            z = int(str(z)[::-1]);
            z = -z;
            if (z<-2**31):
                return(0);
            else:
                return(z);

Explain:

Turn integer into string and then take reverse of the string and then turn it back. Only thing that needs to be careful is if it exceeds the range proposed in the question.

 

Question 6 ZigZag Conversion

The description of the question can be found in the following link:

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

  1. My Code;

微信图片_20200312024858

Explain: The idea is quite clear. For each character in the string, find out which line does is belong to. As we go through the string from left to right and it is exactly the order required in the zigzag conversion, hence we do not need to worry too much about the order of the conversion. We use a dictionary to store the character in each row, and then we put all of them together at the same time in the end. One special case is when the required row number is one, in this case we just need to return the original string.

 

Question 5 Longest Palindromic Substring

The description of the question in the following link

https://leetcode.com/problems/longest-palindromic-substring/submissions/

My Code:

微信图片_20200311003852

Explanation:

As we are looking for the substring, the idea is straightforward: writing a function that checks all the substring with possible length, from 1 to the length of whole string. The only thing that we need to be very careful is about the index of the substring. I have made several mistakes, and I want to summarize some useful situations here.

Assume z is a string, with length k;

  1. z[j] : Take the j+1 th element in the string. (j < k)
  2. z[j:j+i]: Take the substring from j to j+i-1
  3. z[-j]: Take the jth last element of the string (starting from -1)
  4. z[::-1]: Reverse the string
  5. z[i:i] : Gives nothing (null)

Hence the first loop of the code initialize all the possible length, from 1 to total length.

The second loop gives all the possible starting checking point for each i given by the first loop indicator. Hence we may check all the possible substring and determine the longest palindromic substring.

P.S. When I am writing this review, I have an idea that may improve the speed of this code. 1. We may start from the longest substring to shortest. Whenever we find the longest one we do not need to continue the search.

2. Code by another submitter ；

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def check(l, r):
            while 0 <= l <= r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            return s[l + 1:r]
        pals = [check(i, i) for i in range(len(s))] + [check(i, i + 1) for i in range(len(s) - 1) if s[i] == s[i + 1]]
        return sorted(pals, key = len)[-1] if pals else ''

The idea of this code is to start from each element in the string and start the comparison between left and right expansion. The second last line first summand is to check when the centre of the palindromic substring is a single letter and the second summand is to check when the centre of the palindromic substring is two same letters. And the sum is a list with all the palindromic string.  The last line is to do the sort based on the length of the strings and return the last one which has the longest length.

Question 3 Longest Substring

The description of the question is in the following link.

code

The idea is really clear: For the longest substring, different from the longest subsequence, they must be continuous, hence if for the first time we meet a repeated character, we shall abandon all the character before and included the repeated one, because for any string starting before the repeated character, there will always be a repetition in the string. For each time, we take the maximum between the max we have already had and the maximum of sub string we have now.