这次比赛考细节／模拟。

第一题Longest Word in Dictionary

给定一个单词列表，找出最长的一个单词x，使得

x[0:1], x[0:2], ..., x[0:len(x)]

都在该列表中。如果有长度一样的多个答案，返回最小的单词。

我是用trie做的。首先将单词按照长度排序，然后将单词一一放进一个trie中。用trie是因为将单词放入trie中的同时也可以判断单词的前面部分是否在trie里（这也是按长度排序的原因）。

class Solution(object):
    def longestWord(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        words.sort(key=lambda x: len(x))
        tree = {'#': {}}
        ans = ''
        for word in words:
            p = tree
            ok = True
            for c in word:
                if c not in p:
                    p[c] = {}
                ok = ok and '#' in p
                p = p[c]
            p['#'] = {}
            if ok and (len(word) > len(ans) or word < ans):
                    ans = word
        return ans

但是这题用更简单的做法。这是我朋友们的算法：首先将列表变成集合，然后一个一个去掉最后的字母并判断得到的单词是否在集合中。

class Solution(object):
    def longestWord(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        words = set(words)
        ans = ''
        for word in words:
            if len(word) < len(ans):
                continue
            tmp = word
            while tmp in words:
                tmp = tmp[:-1]
            if tmp:
                continue
            if len(word) > len(ans) or word < ans:
                ans = word
        return ans

第二题Accounts Merge

给定一个列表accounts，每个元素accounts[i]是一个字符串列表：accounts[i][0]是账号的名字，剩下的是邮件地址。如果两个账号有同样的邮件，那么这两个账号是同一个人的。现在要求合并所有账号。合并后的账号的每条记录的第一个位置为账号名字，剩下的是排好序的邮件地址。

感觉是模拟：如果两个账号是一个人的则合并。

class Solution(object):
    def accountsMerge(self, accounts):
        """
        :type accounts: List[List[str]]
        :rtype: List[List[str]]
        """
        def merge(accounts):
            email2name = {}
            name2email = {}
            for i, account in enumerate(accounts):
                name = account[0]
                emails = account[1:]
                j = i
                for email in emails:
                    if email in email2name:
                        j = email2name[email]
                        break
                if j not in name2email:
                    name2email[j] = set()
                for email in emails:
                    email2name[email] = j
                    name2email[j].add(email)
            ans = []
            for k, v in name2email.items():
                tmp = [accounts[k][0]]
                tmp.extend(list(v))
                ans.append(tmp)
            return ans
        ans = merge(accounts)
        while True:
            tmp = merge(ans)
            if len(tmp) == len(ans):
                break
            ans = tmp
        return [[a[0]]+sorted(a[1:]) for a in ans]

第三题Remove Comments

给定一个字符串列表source表示一个C++程序，source[i]表示第i行代码。现在要求去除所有注释，并去除空行。

也是模拟：一行一行处理源代码。如果是//注释，情况简单，直接去掉就行。如果是/*注释，那么在去除/* comments */之后还要继续处理剩下来的代码。

class Solution(object):
    def removeComments(self, source):
        """
        :type source: List[str]
        :rtype: List[str]
        """
        ans = []
        multi = False
        i = 0 
        while i < len(source):
            cur = source[i]
            if multi:
                p = cur.find('*/')
                if p == -1:
                    i += 1
                    continue
                cur = cur[p+2:]
                if ans:
                    cur = ans[-1] + cur
                    ans.pop()
                multi = False
            p = cur.find('/*')
            q = cur.find('//')
            if (p == -1 and q >= 0) or (p > q >= 0):
                cur = cur[:q]
            elif (q == -1 and p >= 0) or (q > p >= 0):
                q = cur.find('*/', p+2)
                if q == -1:
                    cur = cur[:p]
                    multi = True
                else:
                    cur = cur[:p] + cur[q+2:]
                    source[i] = cur
                    continue
            if len(cur) > 0:
                ans.append(cur)
            i += 1
        return ans

第四题Candy Crush

给定一个二维数组代表糖果传奇（Candy Crush）的状态，返回消除后的最终状态。

还是模拟：首先找出可以消除的位置，如果没有消除的位置，程序就结束了。如果有消除的位置，将那些位置消除（变成0），然后将悬空的糖果掉落。

class Solution(object):
    def candyCrush(self, board):
        """
        :type board: List[List[int]]
        :rtype: List[List[int]]
        """
        n = len(board)
        m = len(board[0])
        def eliminate():
            ans = set()
            for i in xrange(n):
                for j in xrange(m):
                    if board[i][j] == 0:
                        continue
                    tmp = []
                    k = j
                    while k < m and board[i][j] == board[i][k]:
                        tmp.append((i, k))
                        k += 1
                    if len(tmp) >= 3:
                        ans |= set(tmp)
                    tmp = []
                    k = i
                    while k < n and board[i][j] == board[k][j]:
                        tmp.append((k, j))
                        k += 1
                    if len(tmp) >= 3:
                        ans |= set(tmp)
            if len(ans) == 0:
                return False
            for i, j in ans:
                board[i][j] = 0
            return True

        def fall():
            for j in xrange(m):
                k = n - 1
                for i in xrange(n-1, -1, -1):
                    if board[i][j] != 0:
                        board[k][j] = board[i][j]
                        k -= 1
                for i in xrange(k, -1, -1):
                    board[i][j] = 0

        while eliminate():
            fall()
        return board
leetcode contest