Language: C99 In this problem you will write functions that computes whether or
ID: 3729477 • Letter: L
Question
Language: C99
In this problem you will write functions that computes whether or not two strings s1 and s2 are anagrams of each other. Two non null strings are anagrams of each other if and only if they both have the same number of occurrences of each character. The first two functions below should return true if and only if the parameter strings are anagrams of each other and false otherwise.
a) bool is_anagram_easy(char *s1, char*s2) which runs in at worst O(n²) time. Also, you may not create any additional arrays or strings for this part.
b) bool is_anagram_hard(const char *s1, const char *s2) which runs in at worst O(n) time.
c) char *contains_anagram(char *dictionary[], int len, const char *to_match) which determines whether or not the dictionary contains an anagram of the string to_match. If it does, the function returns the memory address corresponding to the first match inside dictionary and returns NULL otherwise. Analyse the runtime in terms of both len and the size of to_match.
Explanation / Answer
Programm as per instruction :::::::
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
/* Function prototype */
void bubbleSort(char *arr, int n);
char getMax(char *arr, int n);
void radixsort(char *arr, int n);
void countSort(char *arr, int n, int exp);
/* function to check whether two strings are anagram of
each other which runs in at worst O(n²) time */
bool is_anagram_easy(char *s1, char *s2)
{
int n1 = strlen(s1);
int n2 = strlen(s2);
if (n1 != n2)
return false;
// Sort both strings
bubbleSort(s1, n1);
bubbleSort(s2, n2);
// Compare sorted strings
for (int i = 0; i < n1; i++)
if (s1[i] != s2[i])
return false;
return true;
}
/* function to check whether two strings are anagram of
each other which runs in at worst O(n) time */
bool is_anagram_hard(const char *s1, const char *s2)
{
int n1 = strlen(s1);
int n2 = strlen(s2);
if (n1 != n2)
return false;
char str1[n1];
for (int i = 0; i < n1; i++)
str1[i] = s1[i];
char str2[n2];
for (int i = 0; i < n2; i++)
str2[i] = s2[i];
// Sort both strings
radixsort(str1, n1);
radixsort(str2, n1);
// Compare sorted strings
for (int i = 0; i < n1; i++)
if (str1[i] != str2[i])
return false;
return true;
}
/* function to check whether two strings are anagram of
each other which runs in at worst O(n) time */
bool contains_anagram(char *dictionary[], int len, const char *to_match)
{
int n_match = strlen(to_match);
char str_to_match[n_match];
for (int i = 0; i < n_match; i++)
str_to_match[i] = to_match[i];
for(int j = 0; j < len; j++) {
if (is_anagram_hard(dictionary[j], str_to_match)) {
printf("The string match found in dictionary");
return true;
}
}
printf("The string match not found in dictionary");
return false;
}
void exchange(char *a, char *b)
{
char temp;
temp = *a;
*a = *b;
*b = temp;
}
// Radix Sort O(n^2)
void bubbleSort(char arr[], int n)
{
char temp;
// Sorting strings using bubble sort
for (int j=0; j<n-1; j++)
{
for (int i=j+1; i<n; i++)
{
if (arr[j] < arr[i])
{
exchange(&arr[i], &arr[j]);
}
}
}
}
char getMax(char arr[], int n)
{
char mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
// A function to do counting sort
void countSort(char arr[], int n, int exp)
{
char output[n]; // output array
int i, count[10] = {0};
for (i = 0; i < n; i++)
count[ (arr[i]/exp)%10 ]++;
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
for (i = n - 1; i >= 0; i--)
{
output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
count[ (arr[i]/exp)%10 ]--;
}
// Copy the output array to arr[]
for (i = 0; i < n; i++)
arr[i] = output[i];
}
// Radix Sort O(n)
void radixsort(char arr[], int n)
{
// Find the maximum number
int m = getMax(arr, n);
// Do counting sort for every char
for (int exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n, exp);
}
int main()
{
char str1[] = "abcde";
char str2[] = "abced";
printf(" is_anagram_easy - O(n^2) : ");
if (is_anagram_easy(str1, str2))
printf("The two strings are anagram of each other");
else
printf("The two strings are not anagram of each other");
char str3[] = "abcdg";
char str4[] = "abced";
printf(" is_anagram_hard - O(n) : ");
if (is_anagram_hard(str3, str4))
printf("The two strings are anagram of each other");
else
printf("The two strings are not anagram of each other");
printf(" String in dictionary : ");
char* dictionary[5] = {"abcdg", "abcde", "asdfg", "dfgrt", "ertyu"};
char to_match[] = "abcxx";
contains_anagram(dictionary, 5, to_match);
return 0;
}
Output :::::::
is_anagram_easy - O(n^2) : The two strings are anagram of each other
is_anagram_hard - O(n) : The two strings are not anagram of each other
String in dictionary : The string match not found in dictionary
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.