Anagram Detection Problem for a string in Python

(211 Views)


There are many classic problems in programming and this is one of them. It is not much difficult to solve. In this article, you will come to know about anagram and how to find out that a string is an anagram or not. However, before moving on to the solution directly please try to solve it yourself.

What is an Anagram?

An anagram refers to a word or phrase made by reorganizing the letters of another word or phrase. If a string is an anagram of another then it simply means that the word is the reorganization of first. For example listen and silent, heart and earth. To avoid complexity, we can consider that the strings have the same length and prepared from the group of 26 lowercase alphabetic characters and symbols.

Problem Statement and Solution

Our goal is to create programs using sort and compare method, and count and compare method that can help in detecting if a string is an anagram or not. Count and compare method involves some complexity while sort and compare method is a time-efficient one.

Anagram Detection Problem for a string in Python

  1. Sort and Compare
  2. If two strings that are different from each other then they will be considered as anagram only if both contain the same characters. The solution involves receiving a string from the user and storing them in different variables. After that, the strings will be sorted using sorted() and compared to get the end result. If we will start to sort strings alphabetically, we will get the same string if they are anagrams.

    def anagram_sort(sA,sB): alist1 = list(sA) alist2 = list(sB) alist1.sort() alist2.sort() pos = 0 matches = True while pos < len(sA) and matches: if alist1[pos]==alist2[pos]: pos = pos + 1 else: matches = False return matches print(anagram_sort('abcde','edcba'))

    In the above code, you will find that this algorithm looks like O(n) because there is only one iteration for comparing the n characters after sorting. You will find that this algorithm and sorting process will have the same order of magnitude.

  3. Count and Compare
  4. It is much easier than the above method. It considers the fact that any two anagrams have the exact number of a’s, exact number of b’s, exact number of c’s, and many others. To find out that two strings are an anagram or not, count the number of times each character is present. Every time you will observe a particular character, the counter will be stepped up to that position. If in the last, the two lists of the counter have no difference then the strings are anagram.

def anagram_count(sA,sB): c1 = [0]*26 c2 = [0]*26 for i in range(len(sA)): pos = ord(sA[i])-ord('a') c1[pos] = c1[pos] + 1 for i in range(len(sB)): pos = ord(sB[i])-ord('a') c2[pos] = c2[pos] + 1 j = 0 stillOK = True while j<26 and stillOK: if c1[j]==c2[j]: j = j + 1 else: stillOK = False return stillOK print(anagram_count('apple','pleap'))

In this code, there are several iterations in the solution. The two iterations from the start help in counting characters depending on n. The next iteration, which is the third one, compares two lists of counts. Adding all the possible 26 steps provides T(n)=2n+26T(n), meaning O(n). This is how you will get a linear order of magnitude algorithm.

Solution Worked 0 UpvotesUpvote

        

Solution Didn't Worked 0 DownvotesDownvote

        


Comments



Search

Earn Money by Submitting Articles
Start submutting articles. Click here to get started
Play 2048 Game Online

Play Duckhunt Online
Search Tags

    Anagram Detection using Python

    Check if a string is an anagram using python

    python code for anagram verify