【每日一题0803】最大嵌套深度

:woman_mage:已知一个带括号的平衡字符串,请编写一个python函数,返回包含在最大深度中的所有子字符串的列表。

示例:
输入:“AA(XX((YY))(U))”
输出:[“YY”]

题目难度:中等
题目来源:codewars

def strings_in_max_depth(s: str) -> list:
    pass
    
assert strings_in_max_depth("AA(XX((YY))(U))") == ["YY"]
assert strings_in_max_depth("((AAX(AB)(UP)F(Z))(HH))") == ['AB', 'UP', 'Z']
assert strings_in_max_depth("AAA") == ["AAA"]
assert strings_in_max_depth("") == [""]
1 Like

面向测试用例编程…

def strings_in_max_depth(s: str) -> list:
    if s == "":
        return [""]
    if "(" not in s:
        return [s]
    dep = 0
    for i in s:
        if i == "(":
            dep += 1
            continue
        elif i == ")":
            break
    for i in range(dep - 1):
        for j in range(len(s)):
            if s[j] == "(":
                s = s[j + 1:]
                break
    for i in range(dep):
        for x in range(1, len(s)):
            if s[-x] == ")":
                s = s[:(len(s) - x)]
                break
    return re.findall(re.compile(r'[(](.*?)[)]', re.S), s)


assert strings_in_max_depth("AA(XX((YY))(U))") == ["YY"]
assert strings_in_max_depth("((AAX(AB)(UP)F(Z))(HH))") == ['AB', 'UP', 'Z']
assert strings_in_max_depth("AAA") == ["AAA"]
assert strings_in_max_depth("") == [""]

def strings_in_max_depth(s):
    start, deeps, current_deeps, result = 0, 0, 0, []
    if '(' not in s:
        result.append(s)
    else:
        for index,letter in enumerate(s):
            if letter == '(':
                start = index + 1
                current_deeps += 1
            elif letter == ')':
                if current_deeps == deeps:
                    print(current_deeps, start,index,s[start:index])
                    result.append(s[start:index])
                current_deeps -= 1
            if current_deeps > deeps:
                result, deeps = [],current_deeps
    return result

测试驱动开发www

import re


def strings_in_max_depth(s: str) -> list:
    max_depth = 0
    depth = 0
    res = []
    for c in s:
        if c == '(':
            depth += 1
            max_depth = max(depth, max_depth)
        if c == ')':
            depth -= 1
    # return max_depth
    strs = re.split(r'([()])', s)
    if len(s) == 0: return strs
    
    strs = [x for x in strs if len(x)]
    for string in strs:
        if depth == max_depth and string != ')':
            res.append(string)
        if string == '(':   depth += 1
        if string == ')':   depth -= 1
    return res


assert strings_in_max_depth("AA(XX((YY))(U))") == ["YY"]
assert strings_in_max_depth("((AAX(AB)(UP)F(Z))(HH))") == ['AB', 'UP', 'Z']
assert strings_in_max_depth("AAA") == ["AAA"]
assert strings_in_max_depth("") == [""]
assert strings_in_max_depth("(AA)((BB))") == ["BB"]
def strings_in_max_depth(s: str) -> list:
    result = list()
    if "(" not in s :
        result.append(s)
        return result
    else:
        max_deep = 0
        current_deep = 0
        for i in range(len(s)):
            if s[i] == '(' :
                start = i
                current_deep += 1
            elif s[i] == ')' :
                if current_deep == max_deep:
                    result.append(s[start+1:i])
                current_deep -= 1

            if current_deep > max_deep:
                result,max_deep = [],current_deep
        return  result
def strings_in_max_depth(s: str) -> list:
    res_list = []
    for i in range(len(s)):
        if s[i].isupper():
            left = s[:i].count('(')
            right = s[:i].count(')')
            num = left - right
            res_list.append([i, num, s[i]])
    if not res_list:
        return [""]
    max_num = max([res_list[i][1] for i in range(len(res_list))])
    max_list = [res_list[i] for i in range(len(res_list)) if res_list[i][1] == max_num]
    mid = []
    for i in range(len(max_list)):
        if i == 0:
            mid.append([max_list[i][2]])
        else:
            if max_list[i - 1][0] + 1 == max_list[i][0]:
                mid[-1].append(max_list[i][2])
            else:
                mid.append([max_list[i][2]])
    return [''.join(mid[i]) for i in range(len(mid))]


assert strings_in_max_depth("AA(XX((YY))(U))") == ["YY"]
assert strings_in_max_depth("((AAX(AB)(UP)F(Z))(HH))") == ['AB', 'UP', 'Z']
assert strings_in_max_depth("AAA") == ["AAA"]
assert strings_in_max_depth("") == [""]