# Coding Questions - Strings¶

This page will collect all the string related questions.

## Tips in Python¶

1. ‘1’.isdigit() will return True or False
2. num += num*10 + (‘digit’-‘0’) will convert a string to an integer during the traverse

## LeetCode 115. Distinct Subsequences¶

• empty string is a subsequence of any string but only 1 time

• use dp[i][j] to denote # of times the string s[0:j] contains the string t[0:i]

0 1 2 ... j
0 1 1 1 ... 1
0 0 0 0 ... 0
... 0 0 0 ... 0
i 0 0 0 ... 0

The key point in DP solution is to clarify the different meaning of index number between dp[i] and str[i].

dp[i][j]: represents the # of distinct results between S[0:j-1] and T[0: i-1] represents the # of distinct results between S[0:j-2] and T[0: i-1] represents the # of distinct results between S[0:j-2] and T[0: i-2]
• Usually we initialize the dp array with N+1 space, the extra space is to handle corner cases
• When you use the loop to create dp array, the outer loop is for row and inner loop is for col.
• Always put the status that keeps changing in inner loop which is S[j] in this question

This is the source code:

```def numDistinct(self, s, t):
# create extra space for the 0 condition
dp = [[0 for _ in range(len(s) + 1)] for __ in range(len(t) + 1)]

# Initialize the dp array
for i in range(len(s) + 1):
dp[i] = 1

# keep outer loop still, increase the inner loop which is string s
for i in range(1, len(t) + 1):
for j in range(1, len(s) + 1):
dp[i][j] = dp[i][j - 1] if s[j - 1] != t[i - 1] else dp[i - 1][j - 1] + dp[i][j - 1]
return dp[-1][-1]
```

## LeetCode 91. Decode Ways¶

dp[i]: represents the # of decode ways for string S[:i-1], the last char represents the # of decode ways for string S[:i-2], the last 2nd char represents the # of decode ways for string S[:i-3], the last 3rd char
• if S[i-2:i] is 2 digits, then it has 2 ways:
1. S[:i-2]’s ways + S[i-2:i]
2. S[:i-1]’s ways + S[i-1:i]
• if S[i-2:i] isn’t 2 digits, then it only has one decode way:
1. S[:i-1]’s ways + S[i-1:i]

Then the final relationship will be:

```def numDecodings(self, s):
#dp[i] = dp[i-1] if s[i] != "0"
#       +dp[i-2] if "09" < s[i-1:i+1] < "27"
if s == '':
return 0
dp =  +  * (len(s))
for i in range(1, len(s)+1):
if s[i-1] != "0":
dp[i] += dp[i-1]
if i != 1 and '09' < s[i-2:i] < '27':  # this is to handle "10" and "01"ways = 0
dp[i] += dp[i-2]
return dp[-1]
```