“This is the third day of my participation in the First Challenge 2022, for more details: First Challenge 2022”.

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the force button algorithm continued to punch the card 63 days 🎈!
🚀 Algorithm 🚀

🌲 valid letter heterotopic words

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

Note: if each character in S and T occurs the same number of times, s and T are said to be alphabetic allographs.

Example 1:

Enter: s ="anagram", t = "nagaram"Output:true
Copy the code

Example 2:

Enter: s ="rat", t = "car"Output:false
Copy the code

Tip:

  • 1 <= s.length, t.length <= 5 * 104
  • S and T contain only lowercase letters

🌻C# method: one pass

Compare subscript arrays for consistency, used to detect isomorphism of two strings.

Code:

public class Solution {
    public bool IsIsomorphic(string s, string t)
    {
        List<int> indexS = new List<int> (); List<int> indexT = new List<int> ();for (int i = 0; i < s.Length; i++)
            indexS.Add(s.IndexOf(s[i]));

        for (int j = 0; j < t.Length; j++)
            indexT.Add(t.IndexOf(t[j]));

        returnindexS.SequenceEqual(indexT); }}Copy the code

The execution result

By execution time:72Ms, beat out all Java commits82.28% user memory consumption:39MB, beat out all Java commits7.60% of the userCopy the code

🌻Java Method 1: Sort

Thinking analytical

  • T is an allotopic of s is equivalent to “two strings are equal when sorted”. So we can sort strings S and t separately and see if the sorted strings are equal.

  • Moreover, if s and T have different lengths, t must not be an allotopic of S.

Code:

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() ! = t.length()) {return false;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        returnArrays.equals(str1, str2); }}Copy the code

The execution result

By execution time:3Ms, beat out all Java commits74.73% user memory consumption:38.5MB, beat out all Java commits67.34% of the userCopy the code

Complexity analysis

Time: O(nlogn) Space: O(long n )
Copy the code

🌻Java Method 2: hash

Thinking analytical

  • T being an allotopic of S is equivalent to “both strings have the same kind and number of occurrences of characters”.
  • Since the string contains only 26 lower-case letters, we can maintain a frequency array table of length 26. We first iterate over the frequency of characters in string S, then iterate over string T, minus the corresponding frequency in table. If table[I]<0 occurs, T contains an extra character that is not in s. Return false.

Code:

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() ! = t.length()) {return false;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        returnArrays.equals(str1, str2); }}Copy the code

The execution result

By execution time:4Ms, beat out all Java commits45.11% user memory consumption:38.5MB, beat out all Java commits73.10% of the userCopy the code

Complexity analysis

Time: O(nlogn) Space: O(long n )
Copy the code

💬 summary

  • Today is the sixty-third day of force buckle algorithm title punch!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!