题解 | #训练聪明的牛#
训练聪明的牛
https://www.nowcoder.com/practice/971090dbcf5043e295b4ea7f6ec85311
import java.util.*; public class Solution { //依旧是最常规的递归,动态规划可自行尝试修改 HashMap<Character, Integer> map = new HashMap<>(); StringBuilder sb = new StringBuilder(); String[] st; public boolean wordBreak (String s, String[] wordDict) { sb.append(s); st = wordDict; for (int i = 0; i < wordDict.length; i++) { map.put(wordDict[i].charAt(0), i); } return dfs(); } public boolean dfs() { if (sb.length() == 0) { return true; } if (!map.containsKey(sb.charAt(0))) return false; int index = map.get(sb.charAt(0)); int len = st[index].length(); if (sb.length() < len) return false; for (int i = 0; i < len; i++) { if (sb.charAt(0) == st[index].charAt(i)) { sb.deleteCharAt(0); } else { return false; } } return dfs(); } }