每日一道算法题 2020.08.26 回溯法解决递归问题
文章目录
两道题放到一起说
首先是力扣的题 实质上是能转化成树的经典递归题 因为顺序一定 所以思路是先组成HashMap集合 然后把根据输入的字母寻找到路径 在每次搜索后需要删除这次的搜索 所以是回溯 核心是
combination.append(str); recursion(map,list,digits,index+1,combination);
combination.deleteCharAt(index);同样
这道题一样可以用回溯法解决 唯一的区别是输入的方式不同,我的思路是遍历一次字母就删掉该字母
String letter = String.valueOf(str.charAt(i));
StringBuffer stringBuffer = new StringBuffer(str);
stringBuffer.deleteCharAt(i);
stringbuffer.append(letter);这个地方还被好兄弟提醒了
stringbuffer.append(String.valueOf(str.charAt(i)))这样写更简洁也更好理解
最后用回溯解决
recursion(list,index+1,stringBuffer.toString(),stringbuffer);
stringbuffer.deleteCharAt(index);唯一的问题是 如果传入"AA"字符串则可能会有重复输出,所以在最后进行了一次去重,题目上要求了根据字典输出所以用了LinkedHashSet
Set<String> set = new LinkedHashSet<String>();
set.addAll(list);
ArrayList<String> list1 = new ArrayList<String>(set);
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论