Title Link

https://leetcode-cn.com/problems/valid-anagram/

Source code github address

https://github.com/YIMEng-0/DataStructure

1. Title Requirements

Given two strings s and t, write a function to determine whether t is an alphabetic ectopic word of s.

Concept of acronym:
Note: if each character in S and t occurs the same number of times, s and T are called alphabetic words.
The simple understanding is: the two strings are the same in length, each character constituting the string is only arranged in different order, and the specific characters and the number of specific characters are the same;

Example 1:
input: s = "anagram", t = "nagaram"
output: true

Example 2:
input: s = "rat", t = "car"
output: false

2. Train of thought analysis

2.1 method I

Sort each character in the two strings, compare the sorted results, and call arrays The equals () method is sufficient;
Before sorting, you need to convert the string into a char array, so that the child can be sorted easily;

2.2 method II

Use an array to record the frequency of characters in the string. The size of this array is defined as 26. Because there are 26 letters in English, you can count all letter strings;
For string s, record the number of occurrences of each character. Once, the array of recording frequencies will be added to the corresponding position;
For string t, record the number of occurrences of each character. Once, the number of recording frequency will be reduced by one in the corresponding position;
If all the elements in the array of recording frequency are 0, it indicates that the two strings meet the definition of letter ectopic words;

3. Execute code

3.1 code implementation of method 1

    public static boolean isAnagram(String s, String t) {
        // Compare the length of the string. If the length is inconsistent, return false directly
        if (s.length() != t.length()) {
            return false;
        }

        // Convert to character array type to sort a single character array and check whether the elements are the same
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();

        // Sort processing
        Arrays.sort(str1);
        Arrays.sort(str2);

        // Just compare and call the comparison function in Arrays
        return Arrays.equals(str1, str2);
    }

3.2 code implementation of method 2

    public boolean isAnagram1(String s, String t) {
        int[] record = new int[26];

        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();

        for (int i = 0; i < str1.length; i++) {
            record[str1[i] - 'a'] += 1;
        }

        for (int i = 0; i < str2.length; i++) {
            record[str2[i] - 'a'] -= 1;
        }

        for (int i = 0; i < record.length; i++) {
            if (record[i] != 0) {
                return false;
            }
        }

        return true;
    }

4. Problem reflection

4.1. Understanding of for loop in method 2

for (int i = 0; i < str1.length; i++) {
    record[str1[i] - 'a'] += 1;
}

str1 is the result of converting the string s into a char [] array, so that you can easily use the char [] array to operate each character in the string;

i < str1. length; Is the total frequency of all characters in the s string; Each character in the s string can be counted;

record[str1[i] - 'a'] += 1; Writing method
Equivalent to record [STR1 [i] - [a '] + +;
Equivalent to record [STR1 [i] - [a '] = record [STR1 [i] - [a'] + 1; However, the latter may not be as convenient to understand as the former;

record is an int array. Its purpose is to count the number of occurrences of characters in string s and string t

• The character s appears once, and the corresponding position in record is responsible for adding one;
• The character of t string appears once, and the corresponding position in record is responsible for subtracting one;
• When the record array is 0, the increase and decrease are the same, indicating that the definition of letter ectopic words is met;

5. Summary

Through sorting and using record array, the discrimination of letter ectopic words can be realized. The use of record array is a conversion to this problem. The large string is disassembled into small characters, and then the number of characters is counted. When the record elements of the array for counting the number of characters are all 0, it meets the definition of letter ectopic words, and the output result is true;