lintcode入门篇五

158. 两个字符串是变位词

写出一个函数 anagram(s, t) 判断两个字符串是否可以通过改变字母的顺序变成一样的字符串。

样例

样例 1:

输入: s = "ab", t = "ab"
输出: true

样例 2:

输入:  s = "abcd", t = "dcba"
输出: true

样例 3:

输入:  s = "ac", t = "ab"
输出: false

挑战

O(n) 的时间复杂度, O(1) 的额外空间

说明

什么是 Anagram?

  • 在更改字符顺序后两个字符串可以相同
输入测试数据 (每行一个参数)如何理解测试数据?
class Solution:
    """
    @param s: The first string
    @param t: The second string
    @return: true or false
    """
    def anagram(self, s, t):
        # write your code here
        for element in s:
            if element in t:
                t = t.replace(t[t.index(element)],‘‘,1)      ##t = t.replace(element,‘‘,1)和前面的t[t.index(element)]一样的意思
                s = s.replace(s[s.index(element)],‘‘,1)
        if len(t) == 0:
            return  True
        return  False

大致思路:

首先有s和t两个字符串

1.循环s字符串每个字符element,如果s字符串的字符在字符串t中也出现的话,s和t都将移除掉公共的字符elemnt,replace(element,‘‘,1)后面的1代表的是只会移除掉一个值,不会过多移除。如果后面不加参数1,则默认会将全部相同的字符element都替换成‘‘。

2.循环完字符串s所有的字符之后,下一步开始判断len(t)的字符串长度是否移除成功(判断len(s)和len(t)两者之间并无差别),如果len(t)==0的话,则说明移除成功,返回true,否则的话说明还存在不同的或者多余的值,则返回false。