Compare strings with a wildcard operator (*) and randomized order — Anagrams

Question

I have two strings, I want to know if they are equal to each other. However the strings character-order has been randomized. Also certain characters may have been swapped out with a wildcard operator (*). I'm using this for Anagram detection.

---

In this case, I'm trying to get the anagram program I have to say that ab** is an anagram of abba. Right now it can tell if its an anagram if it is literally an anagram like abba and bbaa. Now I'm trying to figure out how to implement wildcard *'s and I have no idea where to start, please help!

What i have so far:

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#define SIZE 5



bool areAnagram(char *str1, char *str2)
{

    int count[SIZE] = {0};
    int i = 0;

    for (i = 0; str1[i] && str2[i];  i++)
    {
        count[str1[i]]++;
        count[str2[i]]--;
    }

    if (str1[i] || str2[i])
    {
         return false;
    }



    for (i = 0; i < SIZE; i++)
    {
        if (count[i])
        {
            return false;
        }
    }

     return true;
}

int main()
{
    char str1[SIZE], str2[SIZE];

    FILE *finput;

    finput = fopen("input.txt", "r");

    fscanf(finput, "%s %s", str1, str2);

    printf("%s\n", str1);
    printf("%s\n", str2);

  if(areAnagram(str1, str2))
  {
        printf("THEY ARE ANAGRAMS\n");
  }
  else
  {
      printf("THEY AREN'T ANAGRAMS\n");
  }
}

Answer 1

Similar to how selection-sort algorithm works, but instead of checking integer value to arrange I'll just use a string comparison to select/remove and add an exception for (*). Iterate through the whole list and viola!

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

int main() {

    char inputString[] = "AB**";//input string (with asterisks)
    char comparisonString[] = "AYYB";//comparison string (without asterisks)

    int inputString_length = strlen(inputString);
    int comparisonString_length = strlen(comparisonString);

    int anagram = 1;//boolean

    if (inputString_length != comparisonString_length) {
        anagram = 0;
    } else {

        int i = 0;
        while ((i < inputString_length) && (anagram == 1)) {

            char *letterToCheck = inputString[0];
            memmove(&inputString[0], &inputString[0 + 1], strlen(inputString) - 0);//remove first character

            int j = 0;
            int comparisonString_length_new = strlen(comparisonString);
            int matchFound = 0;//boolean
            while ((j < comparisonString_length_new) && (matchFound == 0)) {
                char *letterToCompare = comparisonString[j];

                if (letterToCheck == '*') {
                    matchFound = 1;
                }

                if (letterToCheck == letterToCompare) {
                    matchFound = 1;
                    memmove(&comparisonString[j], &comparisonString[j + 1], strlen(comparisonString) - j);//remove matched character
                }

                j++;
            }

            if (matchFound == 0) {
                anagram = 0;
            }


            i++;
        }

    }


    if (anagram == 0) {
        printf("Are NOT Anagrams");
    } else {
        printf("Are Anagrams");
    }

}

Another solution where both input and comparison strings may contain * (Note: This solution below was added by an off-site user and not OP, it has also not been tested nor verified by OP)

#include <stdio.h>

#define CHAR_LEN 4
#define SPECIAL_CHARACTER '*'

int count_special_char(char *string) {
    int i = 0, count = 0;
    for(i = 0; i < CHAR_LEN; i++) {
        if(string[i] == SPECIAL_CHARACTER)
            count++;
    }
    return count;
}

int is_anagram(char *string_a, char *string_b) {
    int i, y;
    int found_count = 0;
    int a_special = count_special_char(string_a);
    int b_special = count_special_char(string_b);

    for(i = 0; i < CHAR_LEN; i++) {
        if(string_a[i] == SPECIAL_CHARACTER) //compare only non-asterisk char
            continue;

        for(y = 0; y < CHAR_LEN; y++) {
            if(string_a[i] == string_b[y]) {
                string_b[y] = '\0' //treat this char as found
                found_count++;
                break;
            }
        }
    }

    if((found_count + a_special + b_special) >= CHAR_LEN)
        return 1;
    else
        return 0;
}

int main() {
    char a[CHAR_LEN] = "**CD";
    char b[CHAR_LEN] = "AB**";

    if(is_anagram(a, b))
        printf("yes\n");
    else
        printf("no\n");

    return 0;
}

A*** and *XYZ is assumed as anagram because first string has 3 * which can represent second string XYZ. And second string has 1 * which can represent first string A. If there are any mistakes do point out and help. Thanks!

Answer 2

On Linux and Posix systems, you might use globbing related functions. See glob(7) and look into glob(3), fnmatch(3), wordexp(3) etc

Look also into regcomp(3)

If you need to write it by yourself, read about finite state machines, context free grammars, regular grammars, regular expressions, parsing.