Guest User

Untitled

a guest
May 23rd, 2018
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.51 KB | None | 0 0
  1. class Solution {
  2. class TrieNode {
  3. boolean isWord = false;
  4. TrieNode[] next = new TrieNode[26];
  5. }
  6.  
  7. public boolean wordBreak(String s, List<String> wordDict) {
  8. // Build suffix trie tree, because
  9. TrieNode root = new TrieNode();
  10.  
  11. for (String word : wordDict) {
  12. TrieNode curr = root;
  13. for (int i = word.length() - 1; i >= 0; i--) {
  14. char c = word.charAt(i);
  15. if (curr.next[(int)(c - 'a')] == null) {
  16. curr.next[(int)(c - 'a')] = new TrieNode();
  17. }
  18.  
  19. curr = curr.next[(int)(c - 'a')];
  20. }
  21. curr.isWord = true;
  22. }
  23.  
  24. // T[i]: whether first i character can break into dictionary words
  25. boolean[] T = new boolean[s.length() + 1];
  26. T[0] = true;
  27.  
  28. for (int i = 1; i <= s.length(); i++) {
  29. // At each char, walking backwards while searching in trie
  30. int j = i;
  31. TrieNode curr = root;
  32.  
  33. while (j > 0) {
  34. int idx = j - 1;
  35. char c = s.charAt(idx);
  36. if (curr.next[(int)(c - 'a')] == null) break;
  37. curr = curr.next[(int)(c - 'a')];
  38.  
  39. if (curr.isWord && T[idx]) {
  40. T[i] = true;
  41. break;
  42. }
  43.  
  44. j--;
  45. }
  46. }
  47.  
  48. return T[s.length()];
  49. }
  50. }
Add Comment
Please, Sign In to add comment