01.02. Check Permutation

Description

Given two strings,write a method to decide if one is a permutation of the other.

Example 1:

Input: s1 = "abc", s2 = "bca"

Output: true

Example 2:

Input: s1 = "abc", s2 = "bad"

Output: false

Note:

1. 0 <= len(s1) <= 100
2. 0 <= len(s2) <= 100

Solutions

Solution 1: Array or Hash Table

First, we check whether the lengths of the two strings are equal. If they are not equal, we directly return false.

Then, we use an array or hash table to count the occurrence of each character in string $s1$.

Next, we traverse the other string $s2$. For each character we encounter, we decrement its corresponding count. If the count after decrementing is less than $0$, it means that the occurrence of characters in the two strings is different, so we directly return false.

Finally, after traversing string $s2$, we return true.

Note: In this problem, all test case strings only contain lowercase letters, so we can directly create an array of length $26$ for counting.

The time complexity is $O(n)$, and the space complexity is $O(C)$. Here, $n$ is the length of the string, and $C$ is the size of the character set. In this problem, $C=26$.

Python3JavaC++GoTypeScriptRustJavaScriptSwift

class Solution:
    def CheckPermutation(self, s1: str, s2: str) -> bool:
        return Counter(s1) == Counter(s2)

1 2 3 4 5 6 7 8 9 10 11 12 13 14