Re: [閒聊] 每日leetcode已回收

看板Marginalman作者JIWP (神楽めあ的錢包)時間1年前 (2024/06/07 15:32)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串330/1553 (看更多)

648. Replace Words 給一組string array dictionary以sentance sentance是由多個單字跟空格所組成請將sentance裡的單字用dictionary裡的root代替若有多個root，請用最短的那個 root就是該單字的前綴字思路: 有兩種(1)用字典樹(2)用hash table (1)字典樹這個就很直觀，用一個字典樹紀錄所有dictionary的單字接著將sentance分成多個單字，一個一個去找最短的root (2)hash table 先將dictionary的單字依照長度排序再用一個hash table依照字首字母去記錄每個單字接著一樣將sentance分成多個單字，一個一個去找最短的root golang code (1)字典樹 type node struct { end int16 char [26]*node } func replaceWords(dictionary []string, sentence string) string { tire := &node{-1, [26]*node{}} res := strings.Builder{} for key, val := range dictionary { head, n := tire, len(val) for i := 0; i < n; i++ { if head.char[val[i]-'a'] == nil { head.char[val[i]-'a'] = &node{-1, [26]*node{}} } head = head.char[val[i]-'a'] } head.end = int16(key + 1) } words := strings.Split(sentence, " ") for _, val := range words { n, found, head := len(val), false, tire for i := 0; i < n; i++ { if head.char[val[i]-'a'] != nil { head = head.char[val[i]-'a'] if head.end > 0 { res.WriteString(dictionary[head.end-1]) found = true break } }else{ break } } if !found { res.WriteString(val) } res.WriteString(" ") } (2)hash table func replaceWords(dictionary []string, sentence string) string { var res strings.Builder slices.SortFunc(dictionary, func(i, j string) int { return len(i) - len(j) }) rec := make([][]string, 26) for _, val := range dictionary { rec[val[0]-'a'] = append(rec[val[0]-'a'], val) } words := strings.Split(sentence, " ") n := len(words) for i := 0; i < n; i++ { found := false for _, val := range rec[words[i][0]-'a'] { if strings.HasPrefix(words[i], val) { res.WriteString(val) found = true break } } if !found { res.WriteString(words[i]) } res.WriteString(" ") } return strings.TrimSpace(res.String()) } -- https://i.imgur.com/r9FBAGO.gif