Write a C++ program where Two or more strings are anagrams if they contain exact
ID: 667222 • Letter: W
Question
Write a C++ program where Two or more strings are anagrams if they contain exactly the same letters, ignoring capitalization, punctuation, and spaces. For example, "Information superhighway" and "New utopia? Horrifying sham" are anagrams, as are "ab123ab" and "%%b b*aa". Note that two lines that contain no letters are anagrams.
DESCRIPTION
Write a program that reads two lines of input from the terminal and determines and reports if the lines are anagrams.
INPUT
Input lines will consist of letters, digits, blanks, and punctuation, like this: "New utopia? Horrifying sham". The maximum length of an input line is 60 characters.
OUTPUT
The program will prompt for two input lines and will report whether or not two lines are anagrams.
ERRORS
Your program may assume that the input is as described; it need not detect any errors.
EXAMPLE
Several runs of the program might look like this:
OTHER REQUIREMENTS
Apply top-down design techniques to design an effective algorithm and to build an intelligible program with good structure. Use functions as appropriate; your program must include at least two functions.
HINTS
Read each input line one character at a time, using cin.get(). Process only the letters. Write a function that deals with one line and call it twice.
Note that the end-of-line character has an ASCII value less than that of any printable character; it signals the end of an input line.
HAND IN
Hand in a design document, user document, annotated tests that demonstrate that the program works, and a summary of your reactions to and experience with this project, as described in About Programming Projects. Remember that the design document must begin with a description of the problem the program solves and must provide enough detail that a naive reader could construct from it a program substantially like yours.
Question: If n is the total number of characters in the two input lines, what can you say about the big-O behavior of your program's time? Justify your observations.
Question: Describe a strategy entirely different from the one you implemented that would also determine if two input lines are anagrams.
Explanation / Answer
Hi,
Below is the solution to your problem:
Program:
#include<iostream>
# define NO_OF_CHARS 60
using namespace std;
void Anagramfinder(char *s)
{
//Declare and initialize an array of 60 number where each position has its respective position with respect to
// 60 different characters
int array[NO_OF_CHARS]={0};
char *s1=s;
//check till end of string till NULL is encountered
while(*s!='')
{
//increment the number of occurance of each char with it equivalent position in the array[60]
array[(int)*s]+=1;
s++;
}
char ans[60];
cout<<" Enter the string to check for anagram=";
cin.getline(ans, 60);
//performing same task done with original input string
int a[60]={0};
bool gotit=true; // gotit indicates if its is anagram
for(int i=0;ans[i]!='';i++)
{
a[(int)ans[i]]+=1;
}
for(int i=0;i<60;i++)
{
if(a[i]!=array[i])
{
gotit=false;
break;
}
}
//if anagram is present prints is anagram else "is not"
if(gotit)
cout<<" The string "<<ans<<" is anagram of"<<s1<<" ";
else
cout<<" The string "<<ans<<" is not anagram of"<<s1<<" ";
}
int main()
{
char s[60];
cout<<" Enter the string =";
cin.getline(s, 60);
Anagramfinder(s);
return 0;
}
Explaination:
This method assumes that the set of possible characters in both strings are small. In the following implementation, it is assumed that the characters are stored using 8 bit and there can be 60 possible characters.
1) Create count arrays of size 60 for both strings. Initialize all values in count arrays as 0.
2) Iterate through every character of both strings and increment the count of character in the corresponding count arrays.
3) Compare count arrays. If both count arrays are same, then return true.
Question: If n is the total number of characters in the two input lines, what can you say about the big-O behavior of your program's time? Justify your observations.
Answer:Time Complexity: O(n2)
Since there are 2 arrays the complexity of this algo is O(n2)
Question: Describe a strategy entirely different from the one you implemented that would also determine if two input lines are anagrams.
Answer:
This can be implemented in a different way as well using the sort algorithm:
Method 1 (Use Sorting)
1) Sort both strings using quick sort
/* Implementation of Quick Sort
A[] --> Array to be sorted
si --> Starting index
ei --> Ending index
*/
2) Compare the sorted strings
Complexity of this algorithm is:Time Complexity: Time complexity of this method depends upon the sorting technique used. In the above implementation, quickSort is used which may be O(n^2) in worst case. If we use a O(nLogn) sorting algorithm like merge sort, then the complexity becomes O(nLogn)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.