Write a C++ program where Two or more strings are anagrams if they contain exact

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:
csci> agm
Enter two lines that might be anagrams:
--> Eleven plus two
--> Twelve plus one
The two strings ARE anagrams.

csci> agm
Enter two lines that might be anagrams:
--> This is a string.
--> Another string
The two strings are NOT anagrams.

csci> agm
Enter two lines that might be anagrams:
--> Snooze alarms
--> Alas, no more Z's.
The two strings ARE anagrams.
   
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

#include <stdio.h>
#include <string.h>

void quickSort(char *arr, int si, int ei);

bool areAnagram(char *str1, char *str2)
{
// Get lenghts of both strings
int n1 = strlen(str1);
int n2 = strlen(str2);

// If lenght of both strings is not same, then they cannot
// be anagram
if (n1 != n2)
return false;

// Sort both strings
quickSort (str1, 0, n1 - 1);
quickSort (str2, 0, n2 - 1);

// Compare sorted strings
for (int i = 0; i < n1; i++)
if (str1[i] != str2[i])
return false;

return true;
}

void exchange(char *a, char *b)
{
char temp;
temp = *a;
*a = *b;
*b = temp;
}

int partition(char A[], int si, int ei)
{
char x = A[ei];
int i = (si - 1);
int j;

for (j = si; j <= ei - 1; j++)
{
if(A[j] <= x)
{
i++;
exchange(&A[i], &A[j]);
}
}
exchange (&A[i + 1], &A[ei]);
return (i + 1);
}

void quickSort(char A[], int si, int ei)
{
int pi; /* Partitioning index */
if(si < ei)
{
pi = partition(A, si, ei);
quickSort(A, si, pi - 1);
quickSort(A, pi + 1, ei);
}
}

int main()
{
char str1[] = "Information superhighway";
char str2[] = "New utopia? Horrifying sham";
if ( areAnagram(str1, str2) )
printf("The two strings are anagram of each other");
else
printf("The two strings are not anagram of each other");

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.