Anagram string c++
Problem
Write a C++ function that takes two strings of the same length as input and return true if the strings are anagrams otherwise returns false. Two strings are anagrams if they are permutations of each other ignoring spaces and capitalization. For example “CAT” and “ACT” are anagrams. Assume the input strings have small letter characters only.
Anagram string algorithm
This is a typical interview question. One solution is to sort each string then compare the sorted strings. If the sorted strings are identical then the input strings are anagrams otherwise they are not. We can borrow the merge sort code to sort the strings effectively in nlogn time then compare the strings in linear time. Another solution is compute unique character frequencies in each string. If the count is the same for each character then they are anagrams. We can use hash tables to efficiently compute character frequencies in each string.
Anagram string program code
Here is anagram strings example code in C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 |
//Includes #include <iostream> using namespace std; //Receives input string and size char* Sort(char* str, int n) { //If the string is only one //character then it is already //sorted if (n == 1) { return str; } else { //Calculate the middle int m = n/2; //Allocate space for the two halves char* a = new char[m]; char* b = new char[n-m]; //Copy the first half of the string to a //and the second half of the string to b for (int i = 0; i < m; i++) a[i] = str[i]; for (int i = m; i < n; i++) b[i-m] = str[i]; //Recursively call the function on the two //halves a = Sort(a, m); b = Sort(b, n-m); //The rest of the code is to merge the sorted //halves int l = 0; int r = 0; int k = 0; while (l < m && r < n-m) { //If the character from the first half //is less than the character of the //second half then push it to the result if (a[l] <= b[r]) { str[k] = a[l]; l++; } //Otherwise push the character from the //second half else { str[k] = b[r]; r++; } k++; } //If the loop above is finished and still //l is less than m then this means there //are characters in the first half that //need to be appended to the result if (l < m) { while (l < m) { str[k] = a[l]; l++; k++; } } //Similarly we need to append those characters //in the second half that were not added if (r < n-m) { while( r < n-m) { str[k] = b[r]; r++; k++; } } //Return the sorted string return str; } } //Returns 1 if s1 and s2 are anagrams //n is the string size int Anagrams(char* s1, char* s2, int n) { //Sort the strings s1 = Sort(s1, n); s2 = Sort(s2, n); //Compare the sorted strings for (int i = 0; i < n; i++) { //if one character is different //then they are not anagrams if (s1[i] != s2[i]) return 0; } //If the sorted strings are identical //then the input strings are anagrams return 1; } //Main function void main() { //Sample strings char str1[] = "cat"; char str2[] = "act"; //Check strings if (Anagrams(str1, str2, 3)) { cout << "They are anagrams" << endl; } else { cout << "They are not anagrams" << endl; } } |
Thanks for visiting. Please use the section below for questions or feedback.
About Author
Mohammed Abualrob
Software Engineer @ Cisco