[300 Bài Code Thiếu Nhi] Valid Anagram

Mô tả bài toán

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Constraints:

• 1 <= s.length, t.length <= 5 * 104
• s and t consist of lowercase English letters.

Giải pháp

Chúng ta có nhiều cách để xử lý bài toán trên

• Đếm số lượng mỗi ký tự trong mỗi chuỗi và so sánh kết quả (mình sử dụng code php do chưa biết nhiều về python)

class Solution {

    /**
     * @param String $s
     * @param String $t
     * @return Boolean
     */
    function isAnagram($s, $t) {
        if(strlen($s) !== strlen($t)) {
            return false;
        }
        $arrS = array_count_values(str_split($s));
        $arrT = array_count_values(str_split($t));

        if($arrS == $arrT) {
            return true;
        }

        return false;
    }
}

• Sắp xếp ký tự trong 2 chuỗi và kiểm tra xem 2 kết quả có giống nhau không (code python)

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """

        if len(s) != len(t) or sorted(s) != sorted(t):
            return False

        return True

• Kiểm tra tần suất xuất hiện của mỗi ký tự trong từng chuỗi. Ban đầu ta tạo ra 1 mảng 26 phần tự đại diện cho các kí tự a-z. Ta lặp qua từng kí tự của mỗi chuỗi, mỗi lần gặp 1 kí tự trong chuỗi s ta sẽ tăng giá trị của kí tự đó trong mảng lên 1, mỗi lần gặp 1 kí tự trong chuỗi t ta sẽ giảm giá trị của kí tự đó trong mảng đi 1. Đến khi kết thúc hết chuỗi, nếu giá trị của các kí tự trong mảng đó đều bằng 0 thì có thể kết luận tần suất xuất hiện các ký tự trong 2 chuỗi là như nhau và có thể kết luận đó là chuỗi Anagram.

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """

        if len(s) != len(t):
            return False
        
        freq = [0] * 26
        for i in range(len(s)):
            freq[ord(s[i]) - ord('a')] += 1
            freq[ord(t[i]) - ord('a')] -= 1
        
        for i in range(len(freq)):
            if freq[i] != 0:
                return False
        
        return True

Ngoài ra ở mỗi cách trên, trước khi thực hiện ta đều cần kiểm tra độ dài 2 chuỗi, nếu độ dài khác nhau có thể kết luận luôn đó không phải là chuỗi anagram.

Trên đây là 1 số cách của mình, nếu có cách giải hay hãy comment để cùng thảo luận nhé.

You need to login in order to like this post: click here