MY JAVA DP SOLUTION. USE DICTIONARY TREE TO STORE DICT


  • 1
    S

    public class Solution {

    	DicTree tree = new DicTree();
        List <String> result = new ArrayList<String>();
    	private int sLen = 0;
    	
    	public List<String> wordBreak(String s, Set<String> dict) {
            Iterator it = dict.iterator();
            DicTree tree = new DicTree();
            
            while(it.hasNext()){
            	tree.insert(it.next().toString());
            }
            	        
            sLen = s.length();
            	
            for(int i=0;i<sLen;i++){
            	char[] arr = s.toCharArray();
            	if(!tree.containChar(arr[i]))
            		return	result;
            }
    
            return dProcess(s,tree);
        }
    	
    	public List<String> dProcess(String str, DicTree tree) {
    		List<String> result = new ArrayList<String>();
    
    		for (int i = 1; i <= str.length(); i++) {
    			List<String> li = new ArrayList<String>();
    
    			if (tree.contain(str.substring(0, i))) {
    				
    				if (str.substring(i).length() == 0) {
    					result.add(str);
    					return result;
    				}else
    					li = dProcess(str.substring(i), tree);
    				
    				for (int j = 0; j < li.size(); j++) {
    					result.add(str.substring(0, i) + " " + li.get(j));
    				}
    			}
    		}
    		return result;
    	}
    		
    	
    	
    	public class DicTree{
    		private Node root;
    		public int height;
    		private boolean[] charDic;
    		
    		DicTree(){
    			root = new Node(' ');
    			height = 0;
    			charDic = new boolean[26];
    		}
    		
    		private class Node{
    			private Node[] son;
    			private boolean isEnd;
    			private char val;
    			
    			Node(char val){
    				this.val = val;
    				son = new Node[26];
    				isEnd = false;					
    			}
    		}
    		
    		public void insert(String str){
    			Node node = root;
    			char[] ch = str.toCharArray();
    			for(int i=0;i<str.length();i++){
    				int index = ch[i] - 'a';
    				if(!charDic[index])
    					charDic[index] = true;
    				if(node.son[index] == null){
    					Node newNode = new Node(ch[i]);
    					node.son[index] = newNode;
    					node = newNode;
    				}else
    					node = node.son[index];
    			}
    			if(str.length()>height)	
    				height = str.length();
    			node.isEnd = true;
    		}
    		
    		public boolean contain(String str){
    			Node node = root;
    			char[] ch = str.toCharArray();
    			for(int i=0; i<str.length();i++){
    				int index = ch[i] - 'a';
    				if(node.son[index] == null)
    					return false;
    				else{
    					node = node.son[index];
    				}
    			}
    			return node.isEnd;
    		}
    		
    		public boolean containChar(char ch){
    			return charDic[ch-'a'];
    		}
    	}
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.