牛客NC181 单词拆分(一)【中等动态规划，前缀树 Java,Go,PHP】

题目

在这里插入图片描述
题目链接：
https://www.nowcoder.com/practice/c0d32c1ce5744472a01b2351a2c2767f

思路

前缀树+动态规划

参考答案Java

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param s string字符串* @param dic string字符串一维数组* @return bool布尔型*/public boolean wordDiv (String s, String[] dic) {//前缀树+动态规划PreTreeNode trie = new PreTreeNode();for (String s1 : dic) {add(trie, s1);}int n = s.length();boolean[] dp = new boolean[n + 1];dp[n] = true;for (int i = n - 1; i >= 0 ; i--) {PreTreeNode cur = trie;for (int j = i; j < n ; j++) {char c = s.charAt(j);cur = cur.nexts.get(c);if (cur == null) break;if (cur.end > 0) {dp[i] = dp[i] | dp[j + 1];}}}return dp[0];}static class PreTreeNode {int pass = 0;int end = 0;Map<Character, PreTreeNode> nexts = new HashMap<>();}public void add(PreTreeNode root, String word) {if (word == null || word.length() == 0) return;PreTreeNode cur = root;cur.pass++;for (int i = 0; i < word.length() ; i++) {char c = word.charAt(i);if (!cur.nexts.containsKey(c))cur.nexts.put(c, new PreTreeNode());cur = cur.nexts.get(c);cur.pass++;}cur.end++;}
}

参考答案Go

package main/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param s string字符串* @param dic string字符串一维数组* @return bool布尔型*/
func wordDiv(s string, dic []string) bool {//前缀树+动态规划trie := &PreTreeNode{0, 0, map[byte]*PreTreeNode{}}for i := 0; i < len(dic); i++ {trie.Add(dic[i])}n := len(s)dp := make([]bool, n+1)dp[n] = truefor i := n - 1; i >= 0; i-- {cur := triefor j := i; j < n; j++ {c := s[j]tmp, ok := cur.nexts[c]if !ok {break}cur = tmpif tmp.End > 0 {dp[i] = dp[i] || dp[j+1]}}}return dp[0]
}type PreTreeNode struct {Pass intEnd  intnexts map[byte]*PreTreeNode
}func (node *PreTreeNode) Add(word string) {if len(word) == 0 {return}cur := nodecur.Pass++for i := 0; i < len(word); i++ {c := word[i]_, ok := cur.nexts[c]if !ok {cur.nexts[c] = &PreTreeNode{0, 0, map[byte]*PreTreeNode{}}}cur = cur.nexts[c]cur.Pass++}cur.End++}

参考答案PHP

<?php/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param s string字符串 * @param dic string字符串一维数组 * @return bool布尔型*/
function wordDiv( $s ,  $dic )
{// 前缀树+动态规划$trie = new Node();foreach ($dic as $word){add($trie,$word);}$n = strlen($s);$dp= array();$dp[$n] = true;for($i=$n-1;$i>=0;$i--){$cur = $trie;for($j=$i;$j<$n;$j++){$c = $s[$j];$cur =$cur->nexts[$c];if($cur==null ||empty($cur))break;if($cur->end >0){$dp[$i]=$dp[$i] ||$dp[$j+1];}}}return $dp[0];
}class Node{public $pass = 0;public $end =0;public $nexts = array();
}//添加到单词到前缀树
function add(&$root,$word){$cur =$root;$cur->pass++;for($i=0;$i<strlen($word);$i++){$c = $word[$i];if(!isset($cur->nexts[$c])){$cur->nexts[$c] = new Node();}$cur = $cur->nexts[$c];$cur->pass++;}$cur->end++;
}