题解 | #单词消消乐#的Python解法

1. 解题思路

常规思路：辅助栈。

首先新建一个辅助栈，然后把第一个单词的所有字符添加进去；
接着判断栈顶元素跟接下来压入的字符是否相同，如果相同则弹出栈顶元素，否则继续压入；
最后循环结束，拼接栈中所有字符。

2. 核心代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param Words string字符串一维数组 
# @return string字符串
#
class Solution:
    def WordsMerge(self , Words ):
        # write code here
        if Words == []:                  #若为空，则返回空串
            return ''
        #创建辅助栈
        stack = []
        #把第一个单词的所有字符依次添加到辅助栈中
        for i in Words[0]:
            stack.append(i)
        #接下来判断栈顶元素和下一个压入元素是否相等
        for j in range(1, len(Words)):
            for char in Words[j]:
                if stack[-1] == char:
                    stack.pop()
                else:
                    stack.append(char)
        #最后当栈不为空时，直接拼接栈中字符串
        if stack:
            strings = ''.join(stack)
            return strings
        else:
            #否则返回空串
            return ''

3. 复杂度分析

时间复杂度： $O(n)$ (因为遍历了所有字符，长度为n)
空间复杂度： $O(n)$ (辅助栈最坏情况就是跟字符串长度一样，都是n)

---------------------------------------------我是巧妙的解法二分割线------------------------------------------------

4. 解法二：哈希表+位运算+数组

4.1 思路

掌柜在玩这个字符消消乐的时候发现这样一个有趣的现象，因为相同字符才会消除，即字符个数一定是在偶数的情况下才会消除，那么只要字符个数最后统计为奇数，就会保留下来，所以只需要拼接奇数位的对应字符就能得到可最后消消乐的单词！！！
具体如下图解：

拼接所有字符
统计每个字符的个数，并判断是奇数还是偶数：
最后拼接所有个数为奇数的对应字符:

4.2 核心代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param Words string字符串一维数组 
# @return string字符串
#
from collections import Counter
class Solution:
    def WordsMerge(self , Words ):
        # write code here
        if Words == []:
            return None
        #这里先拼接所有字符串
        strings = ''.join(Words)
        #接着统计每个字符出现的次数
        count_str = Counter(strings)
        #可以发现只要把为奇数的字符都取出来拼接在一起就是所求的最后消消乐剩的 字符串
        string1 = [] #新建一个存储唯一字符的数组
        for i in count_str.keys():
            if count_str[i] & 1: #运用位运算的按位与运算，进行奇偶数判断；奇数就添加到新建数组中
                string1.append(i)
        #拼接新的字符
        words = ''.join(string1)
        return words

4.3 复杂度分析

时间复杂度： $O(n)$ (只需要遍历一次字符串再插入哈希表中)
空间复杂度： $O(n)$ (新建了一个存储奇数字符的数组)