public boolean wordSegmentation(String s, Set<String> dict) {
        // write your code here
        int n=s.length();
        boolean[]t=new boolean[n+1];
        int ml=0;
        for (String w:dict)
            ml=Math.max(ml,w.length());
        int last=0;
        t[0]=true;
        for (int i=1;i<=n;++i) {
            for (int j=1;i-j>=0&&!t[i];++j) {
                t[i]=t[i-j]&&dict.contains(s.substring(i-j,i));
            }
            if (t[i])
                last=i;
            if (i-last>ml)
                return false;
        }
        return t[n];
    }