[leetcode/lintcode 题解] Google 面试题：合法组合

[hakunamatata11]

给一个单词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

• 按照题目要求，首先保证原串存在于 str 中。
• 每次拼接字符串，正好删去一个字符继续搜索。
• 直至当前字符串长度为 1 返回为 true 。
• 使用 TreeSet 标记，除去重复字符串。

public class Solution { /**
     * @param s: 
     * @param str: 
     * @return: Output whether this combination meets the condition */ Set<String> map = new TreeSet<String>(); public boolean checkWord(String s, String[] str) { // Write your code here
        if (s.length() > str.length) { return false;
        } if (s.length() == 0) { return true;
        } return dfs(s, str);
    } public boolean dfs (String s, String[] str) { int result = 0; for(int i = 0; i < str.length; i++) { if(str[i].equals(s)) {
                result = 1;
            }
        } if (result == 0) { return false;
        } if (s.length() == 1) { return true;
        } //当前的子串要没被访问过的
        if (map.contains(s)) { return false;
        } for (int i = 0; i < s.length(); i++) { //删除一个字母后的下一个子串
            String next = s.substring(0,i) + s.substring(i + 1); if (dfs (next,str)) { return true;
            }
        } //新的子串放入 map，为之后子串检查访问情况
 map.add(s); return false;
    }
}

最后再给大家推荐一门使用的前端课程：《Web 前端工程师 P5-P6》

如果你也有如下疑惑和烦恼

• 我了解基础的 html/css/js，但缺乏深入的技术能力，遇到问题没有有经验的人指点怎么办？
• 前端技术迭代快，可是自学知识不成体系，无法快速跟上技术变化节奏，成长缓慢好苦恼；
• 一直在重复很初级的工作，缺乏项目经验，达不到一线大厂的能力要求，不敢跳槽……

针对这些前端同学的共性问题，也为了帮助前端新手和初级工作者快速建立完整的知识体系，通过实战项目掌握前端面试的思路和技巧，最终拿到像阿里、字节跳动、腾讯、美团这样大厂的 offer 九章算法今年新开发了一门前端工程师培养课程。

不确定好不好，来免费**报名试听**就知道了。