Integer to English Words和Word Br

Integer to English Words

题目：

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

Example 1:

Input: 123
Output: "One Hundred Twenty Three"
Example 2:

Input: 12345
Output: "Twelve Thousand Three Hundred Forty Five"
Example 3:

Input: 1234567
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
Example 4:

Input: 1234567891
Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

思路：

• 细节很多，思维要严密。

解：

func numberToWords(num int) string {
    if num == 0{
        return "Zero"
    }

    unitExternal := []string{"", "Thousand", "Million", "Billion"}
    map19 := make(map[int]string, 0)
    map99 := make(map[int]string, 0)
    map99[2] = "Twenty"
    map99[3] = "Thirty"
    map99[4] = "Forty"
    map99[5] = "Fifty"
    map99[6] = "Sixty"
    map99[7] = "Seventy"
    map99[8] = "Eighty"
    map99[9] = "Ninety"
    map19[1] = "One"
    map19[2] = "Two"
    map19[3] = "Three"
    map19[4] = "Four"
    map19[5] = "Five"
    map19[6] = "Six"
    map19[7] = "Seven"
    map19[8] = "Eight"
    map19[9] = "Nine"
    map19[10] = "Ten"
    map19[11] = "Eleven"
    map19[12] = "Twelve"
    map19[13] = "Thirteen"
    map19[14] = "Fourteen"
    map19[15] = "Fifteen"
    map19[16] = "Sixteen"
    map19[17] = "Seventeen"
    map19[18] = "Eighteen"
    map19[19] = "Nineteen"

    resPart := make([]string, 0)
    for ; num > 0; num /= 1000 {
        numUnit := num % 1000
        if numUnit == 0 {
            resPart = append(resPart,"nil")
            continue
        }
        if len(resPart) == 0 {
            resPart = append(resPart, numberUnder1000(numUnit, map19, map99))
        } else {
            resPart = append(resPart, numberUnder1000(numUnit, map19, map99)+" "+unitExternal[len(resPart)])
        }
    }

    res := ""
    for i := len(resPart) - 1; i >= 0; i-- {
        if resPart[i] == "nil"{
            continue
        }
        if len(res) == 0{
            res += resPart[i]
        }else {
            res += " "+resPart[i]
        }
    }
    return res
}

func numberUnder1000(num int, map19, map99 map[int]string) string {
    if num >= 1000 {
        return ""
    }
    
    res := ""
    if num >= 100 {
        n1 := num / 100
        res += map19[n1] + " " + "Hundred" + " "
    }
    num %= 100
    if num!=0{
        if num < 20 {
            res += map19[num] + " "
        } else {
            n2 := num / 10
            res += map99[n2] + " "
            num %= 10
            if num!=0{
                res += map19[num] + " "
            }
        }
    }
    return res[0 : len(res)-1]
}

Word Break II

题目：

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]
Example 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:

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

思路：

• 回溯法，超时了。

解：（超时的回溯解）

package main

import "strings"

func wordBreak(s string, wordDict []string) ([]string ){
    resCur := make([]string,0)
    res := make([]string,0)
    backtraceWordBreak(s,wordDict,&resCur,&res)
    return res
}

func backtraceWordBreak(s string,wordDict []string,resCur,res *[]string) bool {
    if len(s) == 0{
        str := ""
        for i:=0;i<len(*resCur);i++{
            if i == len(*resCur)-1{
                str += (*resCur)[i]
            }else {
                str += (*resCur)[i]+" "
            }
        }
        *res = append(*res,str)
    }
    for _,word := range wordDict{
        if strings.Index(s,word) == 0{
            subS := s[len(word):]
            
            
            
            
            //TODO
            *resCur = append(*resCur,word)
            backtraceWordBreak(subS,wordDict,resCur,res)
            *resCur = (*resCur)[0:len(*resCur)-1]
        }
    }
    return false
}

解决：

• 先DP，再用DP加速回溯收集解的过程。递归可以快速预测无解情况，直接返回。
• 测试：Runtime: 0 ms, faster than 100.00% of Go online submissions forWord Break II.

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

    resCur := make([]string, 0)
    res := make([]string, 0)
    if dp[len(s)] {
        dfsWordBreak(s, 0, dp, &resCur, &res, wordSet)
    }
    return res
}
func dfsWordBreak(s string, sIdx int, dp []bool, resCur, res *[]string, wordSet map[string]int) {
    //表示的子串为s[0:sIdx]
    if sIdx == len(s) {
        str := ""
        for i := 0; i < len(*resCur); i++ {
            if i == len(*resCur)-1 {
                str += (*resCur)[i]
                break
            }
            str += (*resCur)[i] + " "
        }
        *res = append(*res, str)
        return
    }
    for i := sIdx + 1; i <= len(s); i++ {
        if _, ok := wordSet[s[sIdx:i]]; dp[i] && ok {
            *resCur = append(*resCur, string(s[sIdx:i]))
            dfsWordBreak(s, i, dp, resCur, res, wordSet)
            *resCur = (*resCur)[0 : len(*resCur)-1]
        }
    }
}