“This is the second 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 62 days 🎈!
🚀 Algorithm 🚀

🌲 Example: Isomorphic string

Given two strings s and t, determine whether they are isomorphic.

If the characters in S can be replaced by some mapping to give t, then the two strings are isomorphic.

Each occurrence of a character should map to another character without changing the order of the characters. Different characters cannot be mapped to the same character. The same character can only be mapped to the same character. Characters can be mapped to themselves.

Example 1:

Enter: s ="egg", t = "add"Output:true
Copy the code

Example 2:

Enter: s ="foo", t = "bar"Output:false
Copy the code

Example 3:

Enter: s ="paper", t = "title"Output:true
Copy the code

Tip:

  • We can assume that s and t have the same length.

🌻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: hash

Thinking analytical

We need to judge whether the characters at each position of S and T are one-to-one corresponding, that is, any character of S is corresponding to a unique character in T, and any character of T is corresponding to a unique character in S. This is also known as a “bijective” relationship.

Taking example 2 as an example, although characters A and R in T have a unique mapping O, there are two mappings {a,r} for character O in S, so the conditions are not met.

Therefore, we maintain two hash tables, the first hash table S2T with characters in S as keys and characters mapped to T as values, and the second hash table T2s with characters in T as keys and characters mapped to S as values. Iterating through two strings of characters from left to right, updating two hash tables continuously, If a conflict occurs (that is, the character S [index] corresponding to the current index has been mapped and is not T [index], or the character T [index] corresponding to the current index has been mapped and is not S [index]), the two strings cannot form isomorphism. Returns false.

If there is no conflict at the end of the traversal, the two strings are isomorphic and return true.

Code:

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> s2t = new HashMap<Character, Character>();
        Map<Character, Character> t2s = new HashMap<Character, Character>();
        int len = s.length();
        for (int i = 0; i < len; ++i) {
            char x = s.charAt(i), y = t.charAt(i);
            if((s2t.containsKey(x) && s2t.get(x) ! = y) || (t2s.containsKey(y) && t2s.get(y) ! = x)) {return false;
            }
            s2t.put(x, y);
            t2s.put(y, x);
        }
        return true; }}Copy the code

The execution result

By execution time:24Ms, beat out all Java commits25.02% user memory consumption:38.4MB, beat out all Java commits48.09% of the userCopy the code

Complexity analysis

Time complexity: O(n) Space complexity: O(∣ sigma ∣) where sigma is a character set of strings. The amount of space a hash table can store characters depends on the size of the character set of the string, and at worst each character is different, requiring O(σ ∣).Copy the code

💬 summary

  • Today is the sixty-second day of buckle algorithm clocking!
  • 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!