Check Permutation of two strings

Question

I do have a problem, that I am trying to use the most efficient way to solve it.

"Given two strings, find out if the two strings are permutation of each other."

I do know the straightforward ways to do it (i.e sorting the two strings) etc.

I want to see if my approach will work for all cases, and I am not sure, so I need your opinion and your input.

def CheckPermutaionsBySumUp(firstString, secondString):
   if (len(firstString) != len(secondString)):
      return False

   firstStringCount = 0
   secondStringCount = 0

   for char in firstString:
      firstStringCount += ord(char)

   for char in secondString:
      secondStringCount += ord(char)

   if firstStringCount == secondStringCount:
      return True

   return False

So my approach is that, I do have a constraint that helps here, and is that if the two strings are not of the same length, then the two strings are not permutation of each other.

Then, knowing that each character has a unique number representation, if I sum up the number of each letter for each string using the ord function, I can then compare the two sums and find out if the two strings are permutation. This solution, in my opinion is not only O(n) but also is really space-efficient, than using arrays and data-structures.

My only concern, is there any chance that two strings, with the same length, and with different characters to have the same summation?

yep, that would be a [surjective function](https://en.wikipedia.org/wiki/Surjective_function) — Pynchia, Oct 13 '15 at 21:06
If the question is "how can I solve the problem?", then that is a duplicate. If the question is "why does my code not work for all inputs?", then it needs the appropriate debugging info (including a specific failing input); see https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ and [mre]. If the question is "**does** my code work for all inputs?", then it is off topic; Stack Overflow is not a testing service. — Karl Knechtel, Aug 01 '22 at 21:50

Padraic Cunningham · Answer 1 · 2015-10-13T21:16:35.517

6

If you want an O(n) solution, use the counts of the characters in each string:

from collections import Counter
def is_anagram(a,b):
    if len(a) != len(b):
         return False
    return  Counter(a) == Counter(b)

If you have an anagram the count of and the letters in each string must be identical:

In [45]: is_anagram("foo","oof")
Out[45]: True

In [46]: is_anagram("foobar","raboof")
Out[46]: True

In [47]: is_anagram("foobar","foo")
Out[47]: False

edited Oct 13 '15 at 21:16

answered Oct 13 '15 at 21:12

Padraic Cunningham

176,452
29
245
321

Thank you about this. I would like to know the functionality of the "black-box" as my point is to implement the algorithm, rather than use a function to do it for me. It looks quite interesting, iff I can benefit from learning what is behind it – Phrixus Oct 13 '15 at 21:15
@John, to replicate the logic, create two dicts mapping the letters in each word to the frequency and then compare the letters and counts in the two dicts, also `if len(a) != len(b)` we can simply return False straight away. – Padraic Cunningham Oct 13 '15 at 21:18
I see, this is one of the solutions I found then, if you see my comment in one of the answers bellow! Thank you about this. (Well the user delete his/her answer) – Phrixus Oct 13 '15 at 21:22
1

@PadraicCunningham Sorry, I have removed my answer since it does not fit. Here is John's previous comment: "A simple way but with a need of 2 arrays with integers, and of size 128 if the strings are in ASCII is to increment the values in that array at the position of the character numeric representation and then compare the two arrays." – Pynchia Oct 13 '15 at 21:24
@John, yes same kind of idea, the Counter or a dict approach in general will work for more than just ascii with not much more memory overhead – Padraic Cunningham Oct 13 '15 at 21:28
1

@PadraicCunningham thank you for that, I marked the other's user answer as it was the one answered the actual question, but your answer is also interesting. – Phrixus Oct 13 '15 at 21:28

Jethro Cao · Accepted Answer · 2015-10-13T21:02:59.610

4

Your reasoning, and by extension your method does not hold in general. A quick counterexample:

firstString = 'ad'

secondString = 'bc'

Both strings are of length 2, and the characters sum to a value of 197.

edited Oct 13 '15 at 21:02

answered Oct 13 '15 at 20:59

Jethro Cao

968
1
9
19

1

Fair Enough, sometimes small input makes things much easier than think of the extreme case! Cheers – Phrixus Oct 13 '15 at 21:02

score 1 · Answer 3 · answered Oct 13 '15 at 21:03

1

It is possible for two completely different strings for the same length to have the same summation.

For example:

 '03' # Sum: 99
 '12' # Sum: 99

Think about it this way:

If you increase the value of one character (by writing '1' instead of '0') you only need to decrease the value of another character by the same amount to even it out. Addition of the character values is not sufficient to check for permutations.

answered Oct 13 '15 at 21:03

cg909

2,247
19
23

@John: If you want to keep it in one variable without data structures you can make use of the unlimited size of Python `int`s and put the counts at different "offsets" in the integer with exponentation: stringCount += len(string)**ord(char) – cg909 Oct 13 '15 at 21:26

mohan kumar · Answer 4 · 2016-09-22T10:08:27.483

str1 = raw_input('Enter First String: ')
str2 = raw_input('Enter Second String: ')

def check_permutation(str1, str2):
    if(len(str1) != len(str2)):
        return 'Not Permutation strings'
    #initialize the track_duplicates to 0 to track if the exsisting character at the index of str2 is already matched
    track_duplicates = [0] * len(str2) 
    is_permutations = True
    for c1 in str1:
        c1_in_str2 = False
        i = 0
        for c2 in str2:
            if(c1 == c2 and track_duplicates[i] is 0):
                c1_in_str2 = True
                track_duplicates[i] = 1
                break
            i += 1
        if(not c1_in_str2):
            is_permutations = False
            break
    if(is_permutations):
        return 'Permutation Strings'
    else:
        return 'Not Permutaions Strings'


print(check_permutation(str1, str2))

score 0 · Answer 5 · edited Jun 01 '17 at 09:45

0

def permutation(s1, s2):
    if len(s1) != len(s2): 
        return False
    return ' '.join(sorted(s1)) == ' '.join(sorted(s2))

edited Jun 01 '17 at 09:45

illright

3,991
2
29
54

answered May 31 '17 at 21:34

ASHISH R

4,043
1
20
16

Why using `str.join()` ? Comparing `sorted(s1) == sorted(s2)` will return a `bool` and fulfill the case. NB: `sorted()` will return a sorted string. – Chiheb Nexus Jun 01 '17 at 08:48
@ChihebNexus yes can be done... but this will also work.. its all depends on person to person thinking.. BTW both solutions will work.. – Humble_PrOgRaMeR Jan 09 '22 at 05:11

Check Permutation of two strings

5 Answers5