“Offer comes, ask friends to take it! I am participating in the 2022 Spring Recruit Punch card campaign. Click here for more details.”

📢 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 103rd day 🎈!
🚀 Algorithm 🚀

🌲 Intimacy string

Given two strings s and goal, return true as long as we can get the same result as goal by swapping two letters in S; Otherwise return false.

Swap letters are defined by taking two subscripts I and j (subscripts starting at 0) that satisfy I! = j, then swap the characters at s[I] and s[j].

For example, swapping elements with subscripts 0 and 2 in “abcd” can produce “cbad”.

Example 1:

Enter: s ="ab", goal = "ba"Output:trueExplanation: You can swap s[0] = 'a'And s [1] = 'b'generate"ba"When s and goal are equal.Copy the code

Example 2:

Enter: s ="ab", goal = "ab"Output:falseExplanation: You can only swap s[0] = 'a'And s [1] = 'b'generate"ba"S and goal are not equal.Copy the code

Example 3:

Enter: s ="aa", goal = "aa"Output:trueExplanation: You can swap s[0] = 'a'And s [1] = 'a'generate"aa"When s and goal are equal.Copy the code

Example 4:

Enter: s ="aaaaaaabc", goal = "aaaaaaacb"Output: true,Copy the code

Tip:

  • 1 <= s.length, goal.length <= 2 * 104
  • “S” and “goal” are lowercase letters

🌻C# method: enumeration

Let two strings be s and goal, where S [I] represents the ith character of S and goal[I] represents the ith character of goal.

If s[I]=goal[I], we say I is a match, otherwise I is a mismatch.

The intimacy string is defined as: the i-th character s[I] in S and the j-th character in S need to be swapped, such that I =j, after which S is equal to Goal.

Two strings of an intimate string need to be equal by swapping two characters whose indexes are not equal once.

Code:

public class Solution {
    public bool BuddyStrings(string s, string goal) {
        if(s.Length ! = goal.Length) {return false;
        }
        
        if (s.Equals(goal)) {
            int[] count = new int[26];
            for (int i = 0; i < s.Length; i++) {
                count[s[i] - 'a'] + +;if (count[s[i] - 'a'] > 1) {
                    return true; }}return false;
        } else {
            int first = - 1, second = - 1;
            for (int i = 0; i < goal.Length; i++) {
                if(s[i] ! = goal[i]) {if (first == - 1)
                        first = i;
                    else if (second == - 1)
                        second = i;
                    else
                        return false; }}return(second ! =- 1&& s[first] == goal[second] && s[second] == goal[first]); }}}Copy the code

The execution result

By execution time:84Ms, in all CBeat 47.14% of users in # submissionMemory consumption:37.9MB, in all CBeat 23.70% of users in # submission
Copy the code

🌻Java methods: enumeration

Thinking analytical

Let two strings be s and goal, where S [I] represents the ith character of S and goal[I] represents the ith character of goal.

If s[I]=goal[I], we say I is a match, otherwise I is a mismatch.

The intimacy string is defined as: the i-th character s[I] in S and the j-th character in S need to be swapped, such that I =j, after which S is equal to Goal.

Two strings of an intimate string need to be equal by swapping two characters whose indexes are not equal once.

Code:

class Solution {
    public boolean buddyStrings(String s, String goal) {
        if(s.length() ! = goal.length()) {return false;
        }
        
        if (s.equals(goal)) {
            int[] count = new int[26];
            for (int i = 0; i < s.length(); i++) {
                count[s.charAt(i) - 'a'] + +;if (count[s.charAt(i) - 'a'] > 1) {
                    return true; }}return false;
        } else {
            int first = -1, second = -1;
            for (int i = 0; i < goal.length(); i++) {
                if(s.charAt(i) ! = goal.charAt(i)) {if (first == -1)
                        first = i;
                    else if (second == -1)
                        second = i;
                    else
                        return false; }}return(second ! = -1&& s.charAt(first) == goal.charAt(second) && s.charAt(second) == goal.charAt(first)); }}}Copy the code

The execution result

By execution time:2Ms, beat out all Java commits67.41% user memory consumption:38.4MB, beat out all Java commits15.53% of the userCopy the code

Complexity analysis

Time complexity: O(N), where N is the length of the string Space complexity: O(C), constant space is needed to store the number of character statistics of the string, we count the number of all lowercase letters, so C =26.Copy the code

💬 summary

  • Today is the 103rd day of the buckle algorithm.
  • 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!