[数据结构与算法]Leetcode 389. 找不同

我的思路:

遍历s,建立map,计数.
遍历t,在map中查找每个字母,没找到或者(–计数)为负数,则返回该字母.
时间复杂度:O(n)
空间复杂度:O(n)

官方题解:

题解一:
题目给定了条件,只有26个小写字母.于是使用长度为26的vector即可.
字母-'a’作为vector的下标,值为字母出现次数.扫描一遍s,完成vector.
然后,扫描一遍t.每个字母查找vector,(–计数),如果为负数,则返回该字母.
时间复杂度:O(n)
空间复杂度:O(n)

题解二:
分别遍历s,t. char转为int求和.然后作差,转为char.
时间复杂度:O(n)
空间复杂度:O(1)

小结:
官方题解一:充分利用了题目条件,只有小写字母,可以使用vector.
官方题解二:s与t,注意只有一个不同的字符,记住技巧:char可以转成int求和.