private ArrayList<String> dfs(String s, int n) {
        ArrayList<String> result = new ArrayList<String>(), tmpList, key;
        if( n == 0 ) return result;

        for( int i = 0; i < s.length(); i++ ) {
            String head = s.substring(0, i+1);
            String tail = s.substring(i+1);
            key = new ArrayList<String>();
            key.add( tail );
            key.add( n - 1 + "" );

            if( isValid( head ) ) {
                if( tail.length() == 0 ) {
                    if( n == 1 ) result.add( head );
                    break;
                }

                if( cache.containsKey( key ) ) {
                    tmpList = cache.get( key );
                } else {
                    tmpList = dfs( tail, n - 1 );
                }

                for( String ss : tmpList ) {
                    result.add( head + "." + ss );
                }
            }
        }


        key = new ArrayList<String>();
        key.add( s );
        key.add( n + "" );
        cache.put( key, result );
        return result;
    }