Skip to content

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

Thinking

Two strings are permutations of each other iff they have the same character multiset. Unequal lengths can be rejected immediately; enumerating permutations of \(s_1\) is far more expensive than the input size requires.

The bottleneck is verifying frequencies in linear time. Count characters in \(s_1\), then decrement while scanning \(s_2\): a negative count means the frequencies differ.

The tests use only lowercase letters, so an array of length \(26\) serves as the table. Comparing lengths first avoids counting on inputs that cannot match.

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\).

1
2
3
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
15
16
17
class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        int[] cnt = new int[26];
        for (char c : s1.toCharArray()) {
            ++cnt[c - 'a'];
        }
        for (char c : s2.toCharArray()) {
            if (--cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if (s1.size() != s2.size()) {
            return false;
        }
        int cnt[26]{};
        for (char c : s1) {
            ++cnt[c - 'a'];
        }
        for (char c : s2) {
            if (--cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func CheckPermutation(s1 string, s2 string) bool {
    if len(s1) != len(s2) {
        return false
    }
    cnt := make([]int, 26)
    for _, c := range s1 {
        cnt[c-'a']++
    }
    for _, c := range s2 {
        if cnt[c-'a']--; cnt[c-'a'] < 0 {
            return false
        }
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function CheckPermutation(s1: string, s2: string): boolean {
    if (s1.length !== s2.length) {
        return false;
    }
    const cnt: Record<string, number> = {};
    for (const c of s1) {
        cnt[c] = (cnt[c] || 0) + 1;
    }
    for (const c of s2) {
        if (!cnt[c]) {
            return false;
        }
        cnt[c]--;
    }
    return true;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
impl Solution {
    pub fn check_permutation(s1: String, s2: String) -> bool {
        if s1.len() != s2.len() {
            return false;
        }

        let mut cnt = vec![0; 26];
        for c in s1.chars() {
            cnt[(c as usize - 'a' as usize)] += 1;
        }

        for c in s2.chars() {
            let index = c as usize - 'a' as usize;
            if cnt[index] == 0 {
                return false;
            }
            cnt[index] -= 1;
        }

        true
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var CheckPermutation = function (s1, s2) {
    if (s1.length !== s2.length) {
        return false;
    }
    const cnt = {};
    for (const c of s1) {
        cnt[c] = (cnt[c] || 0) + 1;
    }
    for (const c of s2) {
        if (!cnt[c]) {
            return false;
        }
        cnt[c]--;
    }
    return true;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    func CheckPermutation(_ s1: String, _ s2: String) -> Bool {
        if s1.count != s2.count {
            return false
        }

        var cnt = [Int](repeating: 0, count: 26)

        for char in s1 {
            cnt[Int(char.asciiValue! - Character("a").asciiValue!)] += 1
        }

        for char in s2 {
            let index = Int(char.asciiValue! - Character("a").asciiValue!)
            if cnt[index] == 0 {
                return false
            }
            cnt[index] -= 1
        }

        return true
    }
}

Solution 2: Sorting

Thinking

Frequency counting already answers in \(O(n)\) time, but it uses auxiliary space proportional to the alphabet.

Sorting both strings and comparing them is equivalent and does not assume a small alphabet, at \(O(n \log n)\) cost and with a shorter implementation.

We can also sort the two strings in lexicographical order, and then compare whether the two strings are equal.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the string.

1
2
3
class Solution:
    def CheckPermutation(self, s1: str, s2: str) -> bool:
        return sorted(s1) == sorted(s2)

1
2
3
4
5
6
7
8
9
class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();
        Arrays.sort(cs1);
        Arrays.sort(cs2);
        return Arrays.equals(cs1, cs2);
    }
}

1
2
3
4
5
6
7
8
class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        ranges::sort(s1);
        ranges::sort(s2);
        return s1 == s2;
    }
};

1
2
3
4
5
6
func CheckPermutation(s1 string, s2 string) bool {
    cs1, cs2 := []byte(s1), []byte(s2)
    sort.Slice(cs1, func(i, j int) bool { return cs1[i] < cs1[j] })
    sort.Slice(cs2, func(i, j int) bool { return cs2[i] < cs2[j] })
    return string(cs1) == string(cs2)
}

1
2
3
function CheckPermutation(s1: string, s2: string): boolean {
    return [...s1].sort().join('') === [...s2].sort().join('');
}

1
2
3
4
5
6
7
8
9
impl Solution {
    pub fn check_permutation(s1: String, s2: String) -> bool {
        let mut s1: Vec<char> = s1.chars().collect();
        let mut s2: Vec<char> = s2.chars().collect();
        s1.sort();
        s2.sort();
        s1 == s2
    }
}

1
2
3
4
5
6
7
8
/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var CheckPermutation = function (s1, s2) {
    return [...s1].sort().join('') === [...s2].sort().join('');
};

1
2
3
4
5
6
7
class Solution {
    func CheckPermutation(_ s1: String, _ s2: String) -> Bool {
        let s1 = s1.sorted()
        let s2 = s2.sorted()
        return s1 == s2
    }
}

Comments