Anagram Check Techniques in DSA Python - Execution Trace

Concept Flow - Anagram Check Techniques

Input two strings s1, s2

↓

Check length equal?

No→Return False

Yes↓

Choose technique

↓

Sort & Compare

↓

Compare results

↓

Return True if match, else False

Start by checking if strings have equal length. Then use one of three techniques: sorting both strings and comparing, counting characters with arrays, or using hash maps to count. Finally, compare results to decide if anagrams.

Execution Sample

DSA Python

def are_anagrams(s1, s2):
    if len(s1) != len(s2):
        return False
    return sorted(s1) == sorted(s2)

This code checks if two strings are anagrams by sorting both and comparing.

Execution Table

Step	Operation	s1	s2	Sorted s1	Sorted s2	Comparison Result	Return Value
1	Input strings	listen	silent	-	-	-	-
2	Check length equal	6	6	-	-	-	Continue
3	Sort s1	-	-	e i l n s t	-	-	-
4	Sort s2	-	-	-	e i l n s t	-	-
5	Compare sorted strings	-	-	e i l n s t	e i l n s t	True	-
6	Return result	-	-	-	-	True	True

💡 Strings have equal length and sorted forms match, so return True

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
s1	listen	listen	listen	listen	listen	listen
s2	silent	silent	silent	silent	silent	silent
sorted_s1	-	-	e i l n s t	e i l n s t	e i l n s t	e i l n s t
sorted_s2	-	-	-	e i l n s t	e i l n s t	e i l n s t
comparison_result	-	-	-	-	True	True
return_value	-	-	-	-	-	True

Key Moments - 3 Insights

Why do we check if the lengths of the two strings are equal first?

Because if lengths differ, they cannot be anagrams. This is shown in Step 2 of the execution_table where unequal lengths would cause immediate return False.

Why do we sort both strings before comparing?

Sorting arranges characters in order, so if both sorted strings match exactly (Step 5), they have the same characters in the same counts, confirming an anagram.

Can we just compare the original strings without sorting?

No, because anagrams have same letters but different order. Sorting normalizes order so comparison is valid, as shown in Steps 3-5.

Visual Quiz - 3 Questions

Look at the execution_table, what is the sorted form of s1 at Step 3?

A e i l n s t

B l i s t e n

C s i l e n t

D t s n l e i

💡 Hint

Check the 'Sorted s1' column at Step 3 in the execution_table

At which step does the function decide to return True?

A Step 2

B Step 5

C Step 6

D Step 4

💡 Hint

Look at the 'Return Value' column in the execution_table

If s1 was 'abc' and s2 was 'ab', what would happen at Step 2?

A Continue to sort and compare

B Return True immediately

C Return False immediately

D Error due to different lengths

💡 Hint

Step 2 checks if lengths are equal; if not, returns False

Concept Snapshot

Anagram Check Techniques:
1. Check if strings have equal length.
2. Sort both strings and compare.
3. Alternatively, count characters using arrays or hash maps.
4. Return True if all characters match, else False.
Sorting method is simple and effective for beginners.

Full Transcript

Anagram check starts by verifying if the two input strings have the same length. If not, they cannot be anagrams and the function returns False immediately. If lengths match, one common technique is to sort both strings alphabetically. After sorting, if the two sorted strings are identical, it means both strings have the same characters in the same quantity, so they are anagrams. The function then returns True. This method is straightforward and easy to implement. Other techniques include counting characters using arrays or hash maps, but sorting is often the simplest to understand and visualize.

Practice

1. What does it mean if two strings are anagrams of each other?

easy

A. They contain the same characters in any order

B. They have the same length but different characters

C. They start with the same character

D. They end with the same character

Solution

1. Step 1: Understand the definition of anagrams

   Anagrams are words or phrases made by rearranging the letters of another, so they must have the same characters.

2. Step 2: Compare the character sets

   If two strings have exactly the same characters, just in different orders, they are anagrams.

3. Final Answer:

   They contain the same characters in any order -> Option A

4. Quick Check:

   Anagrams = same characters [OK]

Hint: Check if sorted strings are equal to confirm anagrams [OK]

Common Mistakes:

• Thinking same length means anagrams
• Only checking first or last character
• Ignoring character counts

2. Which of the following Python code snippets correctly checks if two strings s1 and s2 are anagrams using sorting?

easy

A. s1 == s2[::-1]

B. sorted(s1) == sorted(s2)

C. s1.sort() == s2.sort()

D. len(s1) == len(s2)

Solution

1. Step 1: Understand sorting strings in Python

   The sorted() function returns a new sorted list of characters from the string.

2. Step 2: Compare sorted lists for equality

   If sorted(s1) equals sorted(s2), both strings have the same characters in the same counts.

3. Final Answer:

   sorted(s1) == sorted(s2) -> Option B

4. Quick Check:

   sorted strings equal means anagrams [OK]

Hint: Use sorted() to compare strings for anagram check [OK]

Common Mistakes:

• Using .sort() on strings (strings have no sort method)
• Comparing reversed strings instead of sorted
• Only checking length equality

3. What will be the output of the following code?

from collections import Counter
s1 = 'listen'
s2 = 'silent'
print(Counter(s1) == Counter(s2))

medium

A. False

B. TypeError

C. True

D. None

Solution

1. Step 1: Understand Counter usage

   Counter counts the frequency of each character in the string.

2. Step 2: Compare Counters for equality

   Since 'listen' and 'silent' have the same characters with same counts, their Counters are equal.

3. Final Answer:

   True -> Option C

4. Quick Check:

   Counter equality means anagrams [OK]

Hint: Use Counter to count chars and compare for anagrams [OK]

Common Mistakes:

• Expecting False because strings differ in order
• Confusing Counter with sorting
• Not importing collections module

4. Find the error in this anagram check code:

def are_anagrams(s1, s2):
    return s1.sort() == s2.sort()

medium

A. Missing import statement

B. Function should return True always

C. Comparison should be with reversed strings

D. Strings do not have a sort() method

Solution

1. Step 1: Check string methods

   Strings in Python do not have a sort() method; only lists do.

2. Step 2: Identify correct approach

   Use sorted(s1) and sorted(s2) which return sorted lists for comparison.

3. Final Answer:

   Strings do not have a sort() method -> Option D

4. Quick Check:

   sort() not valid on strings [OK]

Hint: Use sorted() on strings, not .sort() method [OK]

Common Mistakes:

• Trying to call .sort() on strings
• Comparing reversed strings instead of sorted
• Ignoring return value of sorted()

5. You want to check if two strings are anagrams but ignore spaces and capitalization. Which code snippet correctly implements this?

hard

A. sorted(s1.lower().replace(' ', '')) == sorted(s2.lower().replace(' ', ''))

B. Counter(s1) == Counter(s2)

C. s1 == s2

D. len(s1) == len(s2)

Solution

1. Step 1: Normalize strings by lowering case and removing spaces

   Use s1.lower().replace(' ', '') and similarly for s2 to ignore case and spaces.

2. Step 2: Sort normalized strings and compare

   Sorting ensures characters are in order for easy comparison.

3. Final Answer:

   sorted(s1.lower().replace(' ', '')) == sorted(s2.lower().replace(' ', '')) -> Option A

4. Quick Check:

   Normalize then sort to check anagrams ignoring spaces/case [OK]

Hint: Lowercase and remove spaces before sorting for anagram check [OK]

Common Mistakes:

• Not removing spaces before comparison
• Not converting to lowercase
• Using Counter without normalization