Leetcode String 151, @Python－CONY的世界

151. Reverse Words in a String

Given an input string, reverse the string word by word.

For example,

Given s = "the sky is blue",
return "blue is sky the".

Success:

56 ms, beats 23.09 % of python submissions

我用最簡單python有提供的split 但是performance不好

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        slist = s.split();
        return " ".join(reversed(slist))

的看到更快的方式是不要reverse，直接用loop -1 就好了，一行搞定

32 ms, beats 85.34 % of python submissions

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        return " ".join(s.split()[::-1])


91. Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Success:

39 ms, beats 86.48 % of python submissions

這題一開始想不到怎麼解，後來也是看官網，用DP

因為是不斷累積的，一旦過程中有一個不能通，整個方法就要作廢 (ex. 12340, 1->2->3->4 -/-> 0 ，因為0不可decode，所以這個方法就不能算了）

所以有個dp 公式是

Count[i] = Count[i-1] if S[i-1] is a valid char ＃算個位數拆法
or = Count[i-1]+ Count[i-2] if S[i-1] and S[i-2] together is still a valid char. ＃算十位數拆法 10-26

注意一下像是1122 這種，112 會有 1->1->2, 11->2, 1->12 這三種，

所以以這字串s[0:3] （=s[0]~s[2]) 來說 dp[0] =1, dp[1] = 2, 在判斷式都成立下，得到dp[2] = dp[0]+dp[1] = 3 是有累積的

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        dp = [0 for x in range(len(s)+1)]
        dp[0] = 1
        for index in range(1, len(s)+1):
            if s[index-1] != '0':
                dp[index] += dp[index-1]
            if  (len(s[index-2:index]) == 2) and (10 <= int(s[index-2:index]) <= 26):
                dp[index] += dp[index-2]

        return dp[len(s)]