CODEWITHSUNDEEP
c++anagram
Xengo
Xengo

Reputation: 435

Anagram Program Testing

My anagram program works great in my dev-cpp but in any online tester throw wrong answer on any testing anagram. Can someone help me?

#include<iostream>
#include<cstring>
using namespace std;

int main()
{

    char input1[10000];
    char input2[10000];
    cin >> input1;
    getchar();
    cin >> input2;
    getchar();

    int leng;
    leng = strlen(input1);
    bool output[leng];

    for(int i=0; i<leng; i++){
            for(int y=0; y<leng; y++){
                    if( input1[i] == input2[y] ){
                        output[i] = true;
                    }
            }
    }

    for(int o=0; o<leng; o++ ){
        if( (o+1) == leng){
            if( output[o] == true){
                 cout << "ano" << endl;
                 break;
            }
        }else if(output[o] == true) {
                 continue;
        }
        cout << "nie" << endl;
        break;
    }


    getchar();
    return 0;
}

Upvotes: 1

Views: 226

Answers (2)

learnvst
learnvst

Reputation: 16195

Rather than trying to reinvent the wheel, there is a neat function is_permutation in <algorithm> that can make this problem trivial . . 

#include <algorithm>

bool isAnagram(std::string a, std::string b) {
    if(a.size() == b.size()) {
        return std::is_permutation ( a.begin(), a.end(), b.begin(), [](char x, char y){return std::tolower(x) == std::tolower(y);} );
    }
    return false;
}

Just remove the binary predictate if you want case sensitivity. Try it here

Upvotes: 1

J&#233;r&#244;me
J&#233;r&#244;me

Reputation: 8066

You have issue with your algorithm. Imagine the following scenario:

Input1: ab
Input2: cdefab

Your algorithm will return OK because it will only check that a & b characters of input1 are present in input2.

Same problem with example such as:

Input1: aaaaaa
Input2: a

Or:

Input1: aaaab
Input2: bbbba

You can change your algorithm by:

  • Counting characters using an array of 256 (index of your character in ASCII) int initialized to 0. Increment for input1 and decrement for input2, in the end your array should be filled with 0. O(n) algo
  • Sorting your two inputs and comparing them character after character. O(n^2) algo

You can find more details about those algo here.

Upvotes: 0

Related Questions