“This is the 17th day of my participation in the First Challenge 2022.
2157. String grouping
The title
You are given an array of strings with indices beginning 00 0 wordsWords words. Each string contains only lowercase English letters. In wordsWords, each letter appears at most once in any substring.
The two strings are said to be associated if we can get the letter set of s2s2 from the letter set of s1s1s1 by one of the following operations:
-
Add a letter to the letter set of s1s1, s1.
-
To delete a letter from the letter set s1s1, s1.
-
Replace one letter in s1s1 s1 with any other letter (or the letter itself). Wordswords can be divided into one or more unintersected groups $. A string and a group belong to that group if either of the following conditions are met:
-
It is associated with at least one other string in the group.
-
It is the only string in this group.
-
Note that you need to make sure that any strings in one group are not associated with any strings in the other groups. It can be proved that the grouping scheme is unique under this condition.
Return an array of length 222 ansansans:
是
After the groupingThe total number of groups.- Ans [1]ans[1]ans[1] is the number of strings contained in the group with the most strings.
Example 1
Input: Words = [" A ","b","ab"," CDE "] Output: [2,3] Explanation: - Words [0] yields words[1] (replacing 'a' with 'b') and words[2] (adding 'b'). So words[0] are associated with words[1] and words[2]. - Words [1] yields words[0] (replacing 'b' with 'a') and words[2] (adding 'a'). So words[1] are associated with words[0] and words[2]. -words [2] yields words[0] (delete 'b') and words[1] (delete 'a'). So words[2] are associated with words[0] and words[1]. - Words [3] is not associated with other strings in words. Therefore, words can be divided into two groups [" A "," B "," AB "] and [" CDE "]. The largest group size is 3.Copy the codeExample 2
Input: Words = [" A "," AB "," ABC "] Output: [1,3] Description: - Words [0] is associated with words[1]. - Words [1] Is associated with words[0] and words[2]. - Words [2] Is associated with words[1]. Because all strings are associated with other strings, they are all in the same group. So the largest group size is 3.Copy the codeAnswer key
Bit operation + hash + and look up set
Why bitwise? This paragraph can be ignored
Each string may need to add, delete, or modify characters; For example, adding a character to the string abcabcabc, deleting a character, or modifying a character, is a bit more complicated to think about if you’re just doing string operations.
Simplify the process of deleting, adding, and modifying strings into 26-bit binaries:
Relationship abcd…. xyzabcd…. xyzabcd…. xyz 1111… 1111111… 1111111… 111
For example: s= ACd =>1101s = ACD =>1101s = ACd =>1101 String from left to right, binary from right to left; By enumerating wordswordswords, you can get the value of the string, and put the value into the hash table mapMapMap
Enumerates mapmapmap, since the value stored in mapmapmap already represents the string in the original array, which is understandable
Get mapMapMap, need string to delete, add, modify operations; We still need bits here
Enumerate the binary between [0,26][0,26][0,26] [0,26] for any string of length greater than 1.
- If the KKK bit is 111, set this position to 000, indicating the deletion operation
- If the KKK bit is 000, set this position to 111, indicating an add operation
- If the KKK bit is 000, this position is set to 111, and one of the other 111 positions is set to 000, indicating substitution
- Add, delete, and modify the value to check whether it exists
中- If so, pass the current value with the added, deleted, or modified value and check the collection
- If it does not exist, do not process it
Enumerate and look up the set data after processing, return and look up the number of groups and the maximum number of groups exist in the set
I’m sorry that the author only has this idea for the time being. The execution time of submitting Leetcode is about 1000MS1000ms, which is quite complicated.
code
var groupStrings = function (words) {
const map = new Map(a)const node = {}
const keyMap = {}
const len = words.length
const heightMap = {}
for (let i = 0; i < len; i++) {
const k = stringToNumber(words[i])
map.set(k, k)
keyMap[words[i]] = k
node[k] = k
heightMap[k] = 0
}
function merge(a, b) {
const x = find(a)
const y = find(b)
if (x === y) return
if (heightMap[x] == heightMap[y]) {
heightMap[x] = heightMap[x] + 1 // add one to the height of the tree
node[y] = x
} else {
if (heightMap[x] < heightMap[y]) {
node[x] = y
} else {
node[y] = x
}
}
}
function find(x) {
if (x === node[x]) return x
node[x] = find(node[x])
return node[x]
}
map.forEach((c) = > {
// We need bits to add and delete
for (let j = 0; j < 26; j++) {
const v = 1 << j
// we need to change the 26-bit binary 0 to 1,1 to 0;
const sign = c & (1 << j)
letk = c - (sign ! = =0 ? v : -v)
if (k && map.has(k)) {
merge(c, map.get(k))
}
}
// Handle the modification,
for (let j = 0; j < 26; j++) {
const v = 1 << j
// Find 1 and delete it
const t = c & v
if(t ! = =0) {
// Find 0 and assign 1
for (let k = 0; k < 26; k++) {
const t2 = c & (1 << k)
if (t2 === 0) {
const key = c + (1 << k) - v
if (key && map.has(key)) {
merge(c, map.get(key))
}
}
}
}
}
})
let rootMap = {}
let max = 0
for (let i = 0; i < len; i++) {
const k = keyMap[words[i]]
const root = find(node[k])
rootMap[root] = (rootMap[root] || 0) + 1
max = Math.max(max, rootMap[root])
}
let l = Object.keys(rootMap).length
return [l, max]
function stringToNumber(s) {
let n = 0
for (let i = 0; i < s.length; i++) {
const t = s[i].charCodeAt() - 97
n = n + (1 << t)
}
return n
}
}
Copy the code