lintcode 1646 · 合法组合【字符串DFS, vip 中等 好题】

题目

https://www.lintcode.com/problem/1646

给一个单词s,和一个字符串集合str。这个单词每次去掉一个字母，直到剩下最后一个字母。求验证是否存在一种删除的顺序，这个顺序下所有的单词都在str中。例如单词是’abc’，字符串集合是{‘a’,’ab’,’abc’},如果删除的顺序是’c’,’b’，那么’abc’,’ab’,’a’都在集合中,就符合条件。输出这个组合是否符合条件.1<=|str[i]|,|s|<=30
1<=str中字符串的个数<=100样例
样例 1:输入：s="abc"，str=["abc","ac","c"]
输出：true
解释：
首先"abc"在`str`里
删除'b',"ac"在`str`里
删除'a',"c"在`str`里
样例 2:输入：s="abc",str=["abc","ab","c"]
输出：false
解释：
"abc"在`str`里
接下来只能删除'c',"ab"在`str`里
由于"a"和"b"都不在`str`里，所以返回false

思路

dfs，递归，动态规划的题是最难的三类了。不太好想。
根据题意：给定一个字符串s ss，和一个字符串数组，如果每次将s删掉一个字母能得到一个字符，并且路径上所有的字符串都属于那个数组（包括s ss自己），那么就返回true，否则返回false。思路是DFS，枚举每次删除的字符即可。代码如下：

代码

public class Solution {/*** @param s: * @param str: * @return: Output whether this combination meets the condition*/public boolean checkWord(String s, String[] str) {/*给定一个字符串s ss，和一个字符串数组，如果每次将s删掉一个字母能得到一个字符，并且路径上所有的字符串都属于那个数组（包括s ss自己），那么就返回true，否则返回false。思路是DFS，枚举每次删除的字符即可。代码如下：*/Set<String> set = new HashSet<>();for (String s1 : str) {set.add(s1);}if(set.size() < s.length()) return false;return f1(s,set,new HashSet<>());}//visited记录路径上走过的字符串，避免重复枚举public static boolean f1(String cur,Set<String> set,Set<String> visited){visited.add(cur);if(!set.contains(cur)) return false;if(cur.length()==1 && set.contains(cur))return true;for (int i = 0; i <cur.length() ; i++) {String next = cur.substring(0,i)+ cur.substring(i+1);//之前走过的字符串就不枚举了if(!visited.contains(next ) && f1(next,set,visited)){return true;}}return false;}
}