|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 糖逗 于 2020-6-9 15:58 编辑
题目描述:
- 实现一个带有buildDict, 以及 search方法的魔法字典。
- 对于buildDict方法,你将被给定一串不重复的单词来构建一个字典。
- 对于search方法,你将被给定一个单词,并且判定能否只将这个单词中一个字母换成另一个字母,使得所形成的新单词存在于你构建的字典中。
- 示例 1:
- Input: buildDict(["hello", "leetcode"]), Output: Null
- Input: search("hello"), Output: False
- Input: search("hhllo"), Output: True
- Input: search("hell"), Output: False
- Input: search("leetcoded"), Output: False
- 注意:
- 你可以假设所有输入都是小写字母 a-z。
- 为了便于竞赛,测试所用的数据量很小。你可以在竞赛结束后,考虑更高效的算法。
- 请记住重置MagicDictionary类中声明的类变量,因为静态/类变量会在多个测试用例中保留。 请参阅这里了解更多详情。
复制代码
- class MagicDictionary {
- private:
- bool isEnd;
- MagicDictionary* next[26];
- public:
- /** Initialize your data structure here. */
- MagicDictionary() {
- isEnd = false;
- memset(next, 0, sizeof(next));
- }
-
- /** Build a dictionary through a list of words */
- void buildDict(vector<string> dict) {
- for(auto cha : dict){
- MagicDictionary* node = this; //注意这块儿的书写!!!!!!!!
- for(auto cha1 : cha){
- if(node -> next[cha1 - 'a'] == NULL){
- node -> next[cha1 - 'a'] = new MagicDictionary();
- }
- node = node -> next[cha1 - 'a'];
- }
- node -> isEnd = true;
- }
- }
-
- /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
- void dfs(bool& res, string& word, MagicDictionary* cur, int sum, int step){
- if(sum > 1 || step > word.size()) return;
- if(step == word.size()){
- if(sum == 1 && cur -> isEnd) res = true;
- return;
- }
- for(int i = 0; i < 26; i++){
- MagicDictionary* temp = cur;//注意这块儿的书写!!!!!!!!
- if(temp -> next[i] != NULL){
- temp = temp -> next[i];
- if(i != word[step] - 'a'){
- dfs(res, word, temp, sum + 1, step + 1);//注意这块儿的书写!!!!!!!!
- }else{
- dfs(res, word, temp, sum, step + 1);
- }
- }
- }
- }
- bool search(string word) {
- bool res = false;
- MagicDictionary* node = this;
- dfs(res, word, node, 0, 0);
- return res;
- }
- };
- /**
- * Your MagicDictionary object will be instantiated and called as such:
- * MagicDictionary* obj = new MagicDictionary();
- * obj->buildDict(dict);
- * bool param_2 = obj->search(word);
- */
复制代码 |
|