boolean wordBreakDFS( String s, Set<String> dict ) {
        boolean result = false;

        for( int i = 0; i < s.length(); i++ ) {
            String head = s.substring(0, i + 1 );
            String tail = s.substring( i + 1 );
            if( dict.contains( head ) ) {
                if( tail.length() == 0 ) {
                    result = true;
                    break;
                }
                if( cache.containsKey( tail ) ) {
                    result = cache.get( tail );
                } else {
                    result = wordBreakDFS( tail, dict );
                }
            }
            if( result ) break;
        }

        cache.put( s, result );
        return result;
    }