2022-06-11

91. Decode Ways

Description

A message containing letters from `A-Z` can be encoded into numbers using the following mapping:

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

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, `"11106"` can be mapped into:

• `"AAJF"` with the grouping `(1 1 10 6)`

• `"KJF"` with the grouping `(11 10 6)`

Note that the grouping `(1 11 06)` is invalid because `"06"` cannot be mapped into `'F'` since `"6"` is different from `"06"`.

Given a string `s` containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

``````Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).``````

Example 2:

``````Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).``````

Example 3:

``````Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").``````

Constraints:

• `1 <= s.length <= 100`

• `s` contains only digits and may contain leading zero(s).

Solution

Approach #0

``````func numDecodings(s string) int {
n := len(s)
a, b, c := 0, 1, 0
for i := 1; i <= n; i++ {
c = 0
if s[i-1] != '0' {
c = b
}
if i > 1 && s[i-2] != '0' && (s[i-2]-'0')*10+(s[i-1]-'0') <= 26 {
c += a
}
a, b = b, c
}
return c
}``````

139. Word Break

Description

Given a string `s` and a dictionary of strings `wordDict`, return `true` if `s` can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

``````Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".``````

Example 2:

``````Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.``````

Example 3:

``````Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false``````

Constraints:

• `1 <= s.length <= 300`

• `1 <= wordDict.length <= 1000`

• `1 <= wordDict[i].length <= 20`

• `s` and `wordDict[i]` consist of only lowercase English letters.

• All the strings of `wordDict` are unique.

Solution

Approach #0

``````func wordBreak(s string, wordDict []string) bool {
m := make(map[string]bool)
for _, word := range wordDict {
m[word] = true
}
dp := make([]bool, len(s)+1)
dp[0] = true
for i := 1; i <= len(s); i++ {
for j := 0; j < i; j++ {
if dp[j] && m[s[j:i]] {
dp[i] = true
break
}
}
}
return dp[len(s)]
}``````

Last updated