class Solution { public int maxLength(List<String> arr) { } }
可以先定义一个int类型的来记录当前最长的长度. 1)回溯法进行遍历判断 2)从list中第一个字符串开始,往后面添加list中下一个(j)字符串 先判断是否含有重复字符,若含有则直接返回, 返回后list删除掉刚才添加的j号字符串 继续添加j+1号位置的字符串继续判断.直至循环完所有字符串 3)若不含有重复字符,则更新当前最长长度,再继续添加下一个字符串,继续进行判断.
private int max; public int maxLength(List<String> arr){ dfs(arr,0,new StringBuilder()); return max; } /** * 先判断传进来的sb是否满足每个字符只出现过一次 * 再对list从start开始添加,添加到sb后面.递归调用此方法 * @param arr * @param start * @param sb * @return */ private void dfs(List<String> arr,Integer start,StringBuilder sb){ //先进行判断是否含有重复字符 if(isRepeat(sb)){ return; } max = Math.max(max, sb.length()); //再继续从start开始遍历,添加到sb后面, //递归调用此方法,继续添加list中下一个字符串进行判断. for(int i = start;i < arr.size();i++){ String s = arr.get(i); sb.append(s); dfs(arr,start+1,sb); sb.delete(sb.length()-s.length(), sb.length()); } } /** * 判断sb是否每个字符只出现一次 * 用一个长度为26的数组记录每个字符出现的次数 * 如果大于1,则重复返回true; * @param sb * @return */ private boolean isRepeat(StringBuilder sb){ int[] count = new int[26]; for(int i=0;i < sb.length();i++){ char c = sb.charAt(i); count[c-97]++; if(count[c-97] > 1){ return true; } } return false; }