Shulou(Shulou.com)06/01 Report--

This article mainly introduces how to solve different problems in leetcode, which has a certain reference value. Interested friends can refer to it. I hope you will gain a lot after reading this article. Let's take a look at it.

Topic link

Https://leetcode-cn.com/problems/find-the-difference/

Topic description

Given the two strings s and t, they contain only lowercase letters.

The string t is randomly rearranged by the string s, and then a letter is added to the random position.

Please find out which letters have been added to t.

Example:

Enter:

S = "abcd"

T = "abcde"

Output:

E

Explanation:

'e'is the letter that was added.

The idea of solving the problem

Tags: hash table

The easiest thing to think of in this question is to use a hash table to iterate over the number of characters that appear in the first string tag, and then subtract the number of characters from the second until it is zero or the original hash table does not exist.

Tags: XOR operation

In addition to the above method, there will be a more tricky solution, which is to use the XOR operation of characters (note that it is not a string). Although it does not reduce the time complexity, it is also an open-minded way to solve the problem.

The use of XOR operations can solve problems mainly because XOR operations have the following characteristics:

A number and 0 to do XOR operation is equal to itself: a ⊕ 0 = a

A number and its own XOR operation is equal to 0 a ⊕ a = 0

XOR operation satisfies commutative law and associative law: a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b

Therefore, on the basis of the above conditions, all the numbers are done or calculated in order, and the final remaining result is the only number.

Time complexity: O (mcm n), m is the length of the string s, n is the length of the string t

Code

Java version

Class Solution {

Public char findTheDifference (String s, String t) {

Char ans = t.charAt (t.length ()-1)

For (int I = 0; I < s.length (); iTunes +) {

Ans ^ = s.charAt (I)

Ans ^ = t.charAt (I)

}

Return ans

}

}

JavaScript version

JavaScript cannot use XOR because it does not have character bit operations. Therefore, the solution of the first hash table is used.

/ * *

* @ param {string} s

* @ param {string} t

* @ return {character}

, /

Var findTheDifference = function (s, t) {

Const map = new Map ()

For (let I = 0; I < s. Stories; iTunes +) {

Const val = map.get (s [I])

Map.set (s [I], val = undefined? 1: val + 1)

}

For (let I = 0; I < t.resume; iTunes +) {

Const val = map.get (t [I])

If (val = 0 | | val = undefined) {

Return t [i]

} else {

Map.set (t [I], val-1)

}

}

}

Drawing and interpretation

Thank you for reading this article carefully. I hope the article "how to solve different problems in leetcode" shared by the editor will be helpful to everyone. At the same time, I also hope that you will support us and pay attention to the industry information channel. More related knowledge is waiting for you to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.