按字典序排列最小的等效字符串~leetcode春季高校编程大赛决赛~python

港控/mmm° 2022-02-16 10:15 173阅读 0赞

题目描述：

> 给出长度相同的两个字符串：`A` 和 `B`，其中 A\[i\] 和 B\[i\] 是一组等价字符。举个例子，如果 `A = "abc"` 且 `B = "cde"`，那么就有 `'a' == 'c', 'b' == 'd', 'c' == 'e'`。
> 
> 等价字符遵循任何等价关系的一般规则：
> 
>  *  自反性：'a' == 'a'
>  *  对称性：'a' == 'b' 则必定有 'b' == 'a'
>  *  传递性：'a' == 'b' 且 'b' == 'c' 就表明 'a' == 'c'
> 
> 例如，`A` 和 `B` 的等价信息和之前的例子一样，那么 `S = "eed"`, `"acd"` 或 `"aab"`，这三个字符串都是等价的，而 `"aab"` 是 `S` 的按字典序最小的等价字符串
> 
> 利用 `A` 和 `B` 的等价信息，找出并返回 `S` 的按字典序排列最小的等价字符串。

**示例 1：**

输入：A = "parker", B = "morris", S = "parser"
    输出："makkek"
    解释：根据A和B中的等价信息，我们可以将这些字符分为 [m,p], [a,o], [k,r,s], [e,i] 共 4 组。每组中的字符都是等价的，并按字典序排列。以答案是 "makkek"。

**示例 2：**

输入：A = "hello", B = "world", S = "hold"
    输出："hdld"
    解释：根据 A和 B 中的等价信息，我们可以将这些字符分为 [h,w], [d,e,o], [l,r] 共 3 组。所以只有 S 中的第二个字符 'o'变成 'd'，最后答案为 "hdld"。

**示例 3：**

输入：A = "leetcode", B = "programs", S = "sourcecode"
    输出："aauaaaaada"
    解释：我们可以把 A 和 B 中的等价字符分为 [a,o,e,r,s,c], [l,p], [g,t]和 [d,m] 共 4 组，因此 S中除了'u'和 'd'之外的所有字母都转化成了'a'，最后答案为"aauaaaaada"。

**提示：**

1.  字符串 `A`，`B` 和 `S` 仅有从 `'a'` 到 `'z'` 的小写英文字母组成。
2.  字符串 `A`，`B` 和 `S` 的长度在 `1` 到 `1000` 之间。
3.  字符串 `A` 和 `B` 长度相同。

\----------------------------------------------------------答题区----------------------------------------------------------

用集合是比较好的方法，total指的是A和B中的所有元素的集合，total26即是26个英文字母的集合，cha就是没有在A，B中出现的字母，我们最后判断S中的字符是否原样输出还是变换输出。

后面主要用到的就是集合的一些运算，交并。先把A，B中一对一对的字母与set\_res列表中的集合做交集运算，如果有交集，就把他们并在一起，否则的话就把这一对字母作为set\_res的一个集合元素。

之后将列表按照集合的长度排列，长的在前，两个循环，再次将有交集的集合做并集运算，另一个清空，每次循环后要把空集合删除，因为如果不删除，列表里是以\{\}存在的，会报错说字典与集合不能做运算。

最后可以判断S中的字母了，如果在cha里就原样输出，如果在set\_res里，就输出这个集合里最小的元素，先把集合变为列表，用min求最小即可，最后将结果列表以字符串输出。

有几个坑感觉需要填一下，第一就是迭代时如何做到删除不想要的元素；第二就是集合的各种运算，挺多的；第三就是如何避免字典被当做集合的这种尴尬。了解的朋友可以一起交流。

class Solution:
        def smallestEquivalentString(self, A: str, B: str, S: str) -> str:
           
            total=set(list(A)+list(B))
            total26={chr(i) for i in range(97,97+26)}
            cha=total26-total
            
            set_res=[]
            for i,j in zip(A,B):
                for k in set_res:
                    if((k&{i,j})!=set()):
                        k.add(i)
                        k.add(j)
                else:
                    set_res.append({i,j})
                    
            set_res.sort(key=lambda x:len(x),reverse=True)
            for j in range(len(set_res)):
                for i in range(j+1,len(set_res)):
                    if(set_res[j]&set_res[i]):
                        set_res[j]=set_res[j]|set_res[i]
                        set_res[i]={}
                while {} in set_res:
                    set_res.remove({})
                
            res=[]
            for i in S:
                if(i in cha):
                    res.append(i)
                else:
                    for j in set_res:
                        if (i in j):
                            res.append(min(list(j)))
            return "".join(res)

如果有帮助的话，为我点个赞！