My easy understood solution, but may not so efficient (accepted)


  • 0
    A

    Based on the work break 1, back to the front, each time search to the end and find possible match!

    public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {
        int length = s.length();
        
        List<List<String>> tail = new ArrayList<List<String>>();
        List<String> temp = null;
        
        for(int i = 0; i < length + 1; i ++)
        {
            tail.add(new ArrayList<String>());
        }
        
        boolean possible[] = new boolean[length + 1];
        possible[length] = true;
        
        for(int i = length - 1; i > -1; i --)
        {
            int position = i;
            
            while(position < length)
            {
                position ++;
                
                if(possible[position] && dict.contains(s.substring(i,position)))
                {
                    temp = tail.get(position);
                    possible[i] = true;
                    
                    if(temp.size() != 0)
                        for(int j = 0; j < temp.size(); j ++)
                            tail.get(i).add(s.substring(i,position) + " " + temp.get(j));
                    else
                        tail.get(i).add(s.substring(i,position));
                }
            }
            
        }
        
        return tail.get(0);
    }
    

    }


Log in to reply
 

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