private static void search(String s, List<String> row, int index, List<List<String>> result){
    
        if (index == s.length()){
            result.add(new ArrayList<String>(row));
            return;
        }
        
        //judge the last element of tem add char is a palindrom
        for (int i = index + 1; i <= s.length(); i++){
        	String prefix = s.substring(index, i);
        	if (!isValid(prefix)){
        		continue;
        	}
            row.add(prefix);
            search(s, row, i, result);
            row.remove(row.size() - 1);
        }
    }