Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- class TrieNode {
- boolean isWord = false;
- TrieNode[] next = new TrieNode[26];
- }
- public boolean wordBreak(String s, List<String> wordDict) {
- // Build suffix trie tree, because
- TrieNode root = new TrieNode();
- for (String word : wordDict) {
- TrieNode curr = root;
- for (int i = word.length() - 1; i >= 0; i--) {
- char c = word.charAt(i);
- if (curr.next[(int)(c - 'a')] == null) {
- curr.next[(int)(c - 'a')] = new TrieNode();
- }
- curr = curr.next[(int)(c - 'a')];
- }
- curr.isWord = true;
- }
- // T[i]: whether first i character can break into dictionary words
- boolean[] T = new boolean[s.length() + 1];
- T[0] = true;
- for (int i = 1; i <= s.length(); i++) {
- // At each char, walking backwards while searching in trie
- int j = i;
- TrieNode curr = root;
- while (j > 0) {
- int idx = j - 1;
- char c = s.charAt(idx);
- if (curr.next[(int)(c - 'a')] == null) break;
- curr = curr.next[(int)(c - 'a')];
- if (curr.isWord && T[idx]) {
- T[i] = true;
- break;
- }
- j--;
- }
- }
- return T[s.length()];
- }
- }
Add Comment
Please, Sign In to add comment