[hero planet July training leetcode problem solving daily] 26th and check the collection

daily

• Today, I checked the collection and thought it was the result of the water problem wa Once .

subject

One 、 Interview questions 17.07. Baby's name

link : Interview questions 17.07. Baby's name

1. Title Description

2. Thought analysis

• The question surface is very clear , In fact, it is to search the set and find all the ancestor nodes ( The word with the smallest dictionary order in the same family ), Then the frequency of each number is counted on the ancestors .
• I wa Once it was union Before judging x,y Dictionary sequence , And then put x Merge to y, This is wrong , Because after path compression ,x Our ancestors and y Forefathers' Dictionary preface is not necessarily who is big and who is small , So it's in union Inside ：x,y Compare the ancestral dictionary order after all paths are compressed , Then select the direction to merge .
• Because my search set template is array , Therefore, we need to discretize words first , Map to digital subscript and search set , More trouble . Next, I plan to sort out a dictionary based template .

---

• The actual measurement is not discretized faster .
• Attention should be paid to the dictionary based joint search set ,findfather and union Before , hold x,y all setdefault In itself
  

3. Code implementation

The original answer

class UnionFind:
    def __init__(self,size):
        self.fathers = list(range(size))
    def find_father(self,x):
        return self._zip_find_father(x)    
    def _zip_find_father(self,x):
        fathers = self.fathers
        if fathers[x] != x:
            fathers[x] = self._zip_find_father(fathers[x])
        return fathers[x]                      
    def union(self,x,y):
        x = self.find_father(x)
        y = self.find_father(y)
        if x == y:
            return False
        if x<y:
            x,y=y,x

        self.fathers[x] = y       
        return True 
    def is_same_father(self,x,y):
        return self.find_father(x)==self.find_father(y)
        
class Solution:
    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:
        # print(names[0].split('('))
        frq = {
    }
        for name in names:
            a = name.split('(')
            b = a[1].split(')')
            frq[a[0]]=int(b[0])
        hashed = sorted(frq.keys())
        n = len(hashed)
        ans =  defaultdict(int)
        uf = UnionFind(n)
        for s in synonyms:
            ss = s.split(',')
            a = ss[0].split('(')[1]
            b = ss[1].split(')')[0]
            x = bisect_left(hashed,a)
            y = bisect_left(hashed,b)
            
            if x<n and y <n:
                uf.union(x,y)
        for a,b in frq.items():
            f = uf.find_father(bisect_left(hashed,a))
            ans[f] += b 
        return [f'{
      hashed[a]}({
      b})' for a,b in ans.items()]

Dictionary based union search set

class UnionFind:
    def __init__(self,eles):
        self.fathers = {
    }
        f = self.fathers
        for e in eles:
            f[e] = e
        
    def find_father(self,x):
        f = self.fathers
        f.setdefault(x,x)
        return self._zip_find_father(x)    
    def _zip_find_father(self,x):
        fathers = self.fathers
        if fathers[x] != x:
            fathers[x] = self._zip_find_father(fathers[x])
        return fathers[x]                      
    def union(self,x,y):
        f = self.fathers
        f.setdefault(x,x)
        f.setdefault(y,y)
        x = self.find_father(x)
        y = self.find_father(y)
        if x == y:
            return False
        if x<y:
            x,y=y,x

        self.fathers[x] = y       
        return True 
    def is_same_father(self,x,y):
        return self.find_father(x)==self.find_father(y)
        
class Solution:
    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]: 
        #  Frequency into the dictionary  
        frq = {
    }
        for name in names:
            a = name.split('(')
            b = a[1].split(')')
            frq[a[0]]=int(b[0])

        #  Build and look up 
        uf = UnionFind(frq.keys())
        for s in synonyms:
            a,b = s[1:-1].split(',') 
            uf.union(a,b)  
            
        #  Build answers 
        ans =  defaultdict(int)
        for a,b in frq.items():
            f = uf.find_father(a)
            ans[f] += b 
        return [f'{
      a}({
      b})' for a,b in ans.items()]