fork(1) download
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. // assume we only work with lowercase letters from a to z
  8.  
  9. string words[] = {"pea", "nut", "butter", "peanut", "a", "but", "ten", "erupt"};
  10. const int WORD_COUNT = sizeof(words)/sizeof(words[0]);
  11. const int NUM_CHARS = 'z' - 'a' + 1;
  12. const int OTHER_CHARS = NUM_CHARS;
  13.  
  14. typedef int OccurrenceCount[NUM_CHARS + 1];
  15. typedef int BitMask;
  16.  
  17. const BitMask ONLY_OTHER_CHARS = (1 << OTHER_CHARS);
  18.  
  19. BitMask words_bm[WORD_COUNT];
  20. typedef vector<string> ResultType;
  21. ResultType anagramWords = ResultType();
  22.  
  23. // return a number in range 0..NUM_CHARS
  24. // OTHER_CHARS is a special code for characters not in 'a'..'z'
  25. inline int charCode(char c) {
  26. unsigned int code = c - 'a';
  27. return code > NUM_CHARS ? OTHER_CHARS : code;
  28. }
  29.  
  30. // BitMask = a bit mask of which characters exists in a string
  31. // it can be used as a quick word filter,
  32. // i.e if a word contains character(s) which are not in the input string,
  33. // then it cannot be a word in the anagram
  34. BitMask getBitMask(const string& s) {
  35. BitMask result = ONLY_OTHER_CHARS; // as we don't care about other characters, always set its bit to 1
  36. for (string::const_iterator iter = s.begin(); iter != s.end(); ++iter) {
  37. result |= (1 << charCode(*iter));
  38. }
  39. return result;
  40. }
  41.  
  42. BitMask getBitMask(const OccurrenceCount& oc) {
  43. BitMask result = ONLY_OTHER_CHARS; // as we don't care about other characters, always set its bit to 1
  44. for (int i = 0; i < NUM_CHARS; ++i) {
  45. if (oc[i]) result |= (1 << i);
  46. }
  47. return result;
  48. }
  49.  
  50. void getOccurrenceCount(const string& s, OccurrenceCount& oc, bool zeroFill = true) {
  51. if (zeroFill) std::fill(oc, oc + NUM_CHARS, 0);
  52. for (string::const_iterator iter = s.begin(); iter != s.end(); ++iter) {
  53. ++oc[charCode(*iter)];
  54. }
  55. }
  56.  
  57. void init()
  58. {
  59. for (int i = 0; i < WORD_COUNT; ++i) {
  60. words_bm[i] = getBitMask(words[i]);
  61. }
  62. }
  63.  
  64. void printOC(const OccurrenceCount& oc)
  65. {
  66. for (int i = 0; i <= NUM_CHARS; ++i) {
  67. if (oc[i] == 0) continue;
  68. cout << char('a' + i) << ": " << oc[i] << ", ";
  69. }
  70. cout << endl;
  71. }
  72.  
  73. void findAnagram(OccurrenceCount& oc, int startIndex = 0)
  74. {
  75. // printOC(oc);
  76. BitMask bitmask = getBitMask(oc);
  77. if (bitmask == ONLY_OTHER_CHARS) { // now the character pool is empty, i.e we have found an anagram
  78. for (ResultType::iterator iter = anagramWords.begin(); iter != anagramWords.end(); ++iter)
  79. cout << *iter << " ";
  80. cout << endl;
  81. return;
  82. }
  83.  
  84. for (; startIndex < WORD_COUNT; ++startIndex) {
  85. // filter words that contain characters not in input
  86. if ((bitmask | words_bm[startIndex]) != bitmask) continue;
  87.  
  88. const string& word = words[startIndex];
  89.  
  90. // update <oc> to exclude characters in <word>
  91. bool wordOk = true;
  92. for (string::const_iterator iter = word.begin(); iter != word.end(); ++iter) {
  93. if (--oc[charCode(*iter)] < 0) wordOk = false; // the character pool cannot allocate this word
  94. }
  95.  
  96. if (wordOk) {
  97. //cout << "-word: " << word << endl;
  98. anagramWords.push_back(word);
  99. findAnagram(oc, startIndex);
  100. // return the anagramWords to its original state
  101. anagramWords.pop_back();
  102. }
  103. // as with any backtracking algorithm, we have to recover the global states, in this case <oc>
  104. for (string::const_iterator iter = word.begin(); iter != word.end(); ++iter) {
  105. ++oc[charCode(*iter)];
  106. }
  107. }
  108. }
  109.  
  110. int main() {
  111. init();
  112.  
  113. string inputString = "peanutbutterpeanutbutter";
  114. OccurrenceCount oc = {0};
  115. getOccurrenceCount(inputString, oc, false);
  116. findAnagram(oc, 0);
  117.  
  118. return 0;
  119. }
Success #stdin #stdout 0s 3464KB
stdin
Standard input is empty
stdout
pea pea nut nut butter butter 
pea nut butter butter peanut 
pea nut butter a but ten erupt 
butter butter peanut peanut 
butter peanut a but ten erupt 
a a but but ten ten erupt erupt