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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

思路

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

代码

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41