This is the 13th day of my participation in the August More Text Challenge. For details, see:August is more challenging
Today, I would like to share with you the next LeetCode easy difficulty title [effective letter ectopes](leetcode-cn.com/problems/tr…).
The title
Given two strings, s and t, write a function to determine whether t is a letter ectopic of S.
Note: if each character in s and T occurs the same number of times, s and t are said to be alphabetic ectopes.
Example 1: Input: s = "anagram", t = "nagaram" Output: true Example 2: Input: s = "rat", t = "car" Output: falseCopy the code
Analysis of the
1. Alphabets,
1. Letters must appear the same number of times
2. All lowercase words
3. The length of the string may be different
Return true if yes, false if no
solution
1. Rank of violence
2.hashMap
Solution a:violence
Train of thought1.First sort2.Iteration compares */ one by onevar isAnagram = function (s, t) {
// Sort the string first
const sArr = s.split("");
const tArr = t.split("");
// If the length is different, it must be false
if(tArr.length ! == sArr.length) {return false;
}
// Sort separately
sArr.sort((a, b) = > {
return a.localeCompare(b);
});
tArr.sort((a, b) = > {
return a.localeCompare(b);
});
for (let i = 0; i < sArr.length; i++) {
if(tArr[i] ! == sArr[i]) {// Return false if not
return false; }}return true;
};
/* Complexity time O(N logN) iteration is N sort is logN space O(1) */
Copy the code
Method 2:hashMap
Train of thought1.HashMap Indicates the number of letters2.Once found the number of statistics is less than0It must befalse, because in the case of identical characters in the string, an extra character will result in one less character */var isAnagram = function (s, t) {
const map = new Map(a);// If the length is different, it must be false
if(t.length ! == s.length) {return false;
}
for (const char of s) {
if (map.has(char)) {
map.set(char, map.get(char) + 1);
} else {
map.set(char, 1); }}for (const char of t) {
if(! map.has(char)) {return false;
}
map.set(char, map.get(char) - 1);
if (map.get(char) < 0) {
return false; }}return true;
};
/* Complexity time O(n) space O(n) */
Copy the code
conclusion
This question examines the use of HashMap and counts repeated characters. Since the query complexity of HashMap is O(1), the time complexity can be reduced very well
Of course, you can sort and then compare one by one
You can look at a column I share (front-end algorithm) there are more questions about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me a like, thank you very much
Anyone interested in “TS” can check out my column (TypeScript common knowledge), thanks for your support
The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Part of the material in this article comes from the network. If there is infringement, please contact delete, [email protected]