June 29, 2018
Check if two strings are permutations in python
Problem
Write an algorithm in Python to check if two strings are permutations of each other
Solution
Let us differentiate between permutations and combinations. An easy way is to think about permutations in terms of lists and combinations in terms of sets. Take a look at the code snippets below…
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
# These two strings are permutations of each other string1 = "CAT" string2 = "ACT" # If we create two lists out of these strings # the lists will be different but if we create # sets out of these strings we will get the same set list1 = list(string1) list2 = list(string2) print(list1) print(list2) # This will print False print(list1 == list2) set1 = set(string1) set2 = set(string2) print(set1) print(set2) # This will print True print(set1 == set2) # In order to check if two strings are permuations # one solution is to convert each string into a set # and see if both produce the same set def checkPermSet(str1, str2): return set(str1) == set(str2) # This will print true print(checkPermSet(string1, string2)) # Another solution is count the number of occurrences # of each character in both strings, if the counts match # then the two strings are permutations. def checkPermDict(str1, str2): # If the length is not the same # then they are not permutations if len(str1) != len(str2): return False # define dictionaries dic1 = {} dic2 = {} # Initialize counts to 0 for c in str1: dic1[c] = 0 for c in str2: dic2[c] = 0 # Calcualte character counts for c in str1: dic1[c]+= 1 for c in str2: dic2[c]+= 1 # Compare counts for c, count in dic1.items(): # If there is a key or count mismatch # then they are not permutations if c not in dic2 or count != dic2[c]: return False # If we reach this point the two strings # are permutations return True # This will print True print(checkPermDict(string1, string2)) |
Thanks for visiting. Please use the comments section below for feedback
About Author
Mohammed Abualrob
Software Engineer @ Cisco