数据结构学习-python实现01--0401

第一种：逐字检查法：
def anagramSolution(s1, s2):
    if len(s1) == len(s2):  # 先查长短，快速判断
        alist = list(s2)  # 字符串可以索引，但不可变，将其变为列表
        pos1 = 0  # 位置参数
        stillOK = True  # 判别条件，由于需要跳出条件控制，及最终返回值
        while pos1<len(s1) and stillOK:
            pos2 = 0
            found = False  # 查找到具体值时使用的标记
            while pos2<len(alist) and not found:
                if s1[pos1] == alist[pos2]:
                    found = True
                else:
                    pos2 += 1
            if found:
                alist[pos2] = None
            else:
                stillOK = False
            pos1 += 1
        return stillOK
    else:
        return False
# 遇到的坑：
# 1、我在 if found 处缩进出了问题，当有重复字母时，不能识别，注意缩进，保证一次循环，只更改一个位置的值
# 2、忘记pos1 += 1，导致死循环，由于之前总是用for循环，导致使用while时忘记停止条件。

第二种算法：排序比较，老师说时间复杂度较高，sort（）排序会比较耗时。
def sortword(s1, s2):
    alist = list(s1)
    blist = list(s2)
    
    alist.sort()
    blist.sort()
    pos = 0
    matches = True
    while pos<len(s1) and matches:
        if alist[pos] == blist[pos]:
            pos +=1
        else:
            matches = False
    return maches

第三种：计数比较法，相对最快。
def numcount(s1, s2):
    c1 = [0] * 26
    c2 = [0] * 26
    for i in range(len(s1)):
        pos = ord(s1[i]) - ord('a')  # 用ASCII码值标记位置
        c1[pos] += 1
    for i in range(len(s2)):
        pos = ord(s2[i]) - ord('a')
        c2[pos] += 1
    j = 0
    stillok = True
    while j < 26 and stillok:  # 判断每个字母出现的次数是否相同
        if c1[j] == c2[j]:
            j += 1
        else:
            stillok = False
    return stillok

# 一个基本的栈结构：用列表来实现栈，列表前段为栈底，后端为栈顶，这样使用append、pop会更快O(1)的复杂度
class Stack:
    def __init__(self):  # 创建栈，首先为空栈
        self.items = []
        
    def isEmpty(self):  # 判断栈是否为空，需要返回值，True/False
        return self.items == []
    
    def push(self, item):  # 入栈操作，不需要返回值，加入栈顶
        self.items.append(item)
        
    def pop(self):  # 出栈操作，有返回值，移除栈顶元素
        return self.items.pop()
    
    def peek(self): # 查看栈顶元素， 有返回值
        return self.items[len(self.items)-1]
    
    def size(self):  # 查看站内元素数，有返回值
        return len(self.items)

# 利用栈判断括号闭合情况
def symbolChecker(symbolString):
    s = Stack()  # 首先建立一个空栈
    balanced = True  # 假设栈括号是对应的。
    index = 0  # 利用索引
    
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol in '({[':  # 入栈判断
            s.push(symbol)
        else:
            if s.isEmpty():  # 判断栈是否为空，在此处的括号，让我纠结了一小时，为什么没判断正确。
                balanced = False
            else:
                top = s.pop()
                if not matches(top, symbol):
                    balanced = False
        index += 1
                
    if balanced and s.isEmpty():
        return True
    else:
        return False
    
def matches(open, close):  # 栈顶的括号，需要和新出现的括号配对，才能证明其正确性。此处利用位置匹配
    opens = '([{'  # 位置对应
    closers = ')]}'  # 位置对应
    return opens.index(open) == closers.index(close)
    
    
print(symbolChecker('({{}})'))

# 查错办法：1.在有输出结果处打印变量，检查哪里的分支没有进入。检查未进入原因，修改代码！