给一个单词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 九章算法今年新开发了一门前端工程师培养课程。
不确定好不好，来免费**报名试听**就知道了。
Select Language