Advertisement
Guest User

Untitled

a guest
Oct 14th, 2019
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.78 KB | None | 0 0
  1. class MagicDictionary {
  2. public:
  3. /** Initialize your data structure here. */
  4. unordered_map<string, int> sets;
  5. MagicDictionary() {
  6.  
  7. }
  8.  
  9. /** Build a dictionary through a list of words */
  10. void buildDict(vector<string> dict) {
  11. for(int i = 0; i < dict.size(); i++)
  12. {
  13. sets[dict[i]]++;
  14. for(int j = 0; j < dict[i].size(); j++)
  15. {
  16. char c = dict[i][j];
  17. dict[i][j] = '*';
  18. sets[dict[i]]++;
  19. dict[i][j] = c;
  20. }
  21. }
  22. }
  23.  
  24. /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
  25. bool search(string word) {
  26.  
  27. if(sets.find(word) != sets.end())
  28. {
  29. for(int i = 0; i < word.size(); i++)
  30. {
  31. char c = word[i];
  32. word[i] = '*';
  33. sets[word]--;
  34. word[i] = c;
  35. }
  36. }
  37. string temp = word;
  38. for(int i = 0; i < word.size(); i++)
  39. {
  40. char c = word[i];
  41. word[i] = '*';
  42.  
  43. if(sets[word] > 0 )
  44. return true;
  45. word[i] = c;
  46. }
  47. word = temp;
  48. if(sets.find(word) != sets.end())
  49. {
  50. for(int i = 0; i < word.size(); i++)
  51. {
  52. char c = word[i];
  53. word[i] = '*';
  54. sets[word]++;
  55. word[i] = c;
  56. }
  57. }
  58. return false;
  59. }
  60. };
  61.  
  62. /**
  63. * Your MagicDictionary object will be instantiated and called as such:
  64. * MagicDictionary* obj = new MagicDictionary();
  65. * obj->buildDict(dict);
  66. * bool param_2 = obj->search(word);
  67. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement