首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

包含我需要的所有符号的字符串的最小片段

要找到一个包含所有符号的最小片段,可以使用滑动窗口算法来解决这个问题。以下是一个解答示例:

滑动窗口算法步骤:

  1. 创建一个空的集合或字典,用于存储目标字符串中所有的符号。
  2. 初始化滑动窗口的起始位置、最小片段长度和最小片段起始位置。
  3. 遍历目标字符串,将符号逐个添加到集合或字典中。
  4. 当集合或字典中的符号数等于目标字符串中所有符号数时,执行以下操作:
    • 计算当前滑动窗口长度,如果比最小片段长度小,则更新最小片段长度和最小片段起始位置。
    • 从滑动窗口的起始位置开始移除符号,直到集合或字典中的符号数不再等于目标字符串中所有符号数。
    • 更新滑动窗口的起始位置,继续遍历下一个符号。
  • 返回最小片段。

示例代码:

代码语言:txt
复制
def find_smallest_substring(target_str: str) -> str:
    symbols = set(target_str)  # 存储目标字符串中的符号
    symbol_count = len(symbols)  # 目标字符串中符号的总数
    window_start = 0  # 滑动窗口的起始位置
    window_len = float('inf')  # 最小片段长度
    min_start = 0  # 最小片段起始位置
    current_symbols = {}  # 当前滑动窗口中的符号

    for window_end in range(len(target_str)):
        symbol = target_str[window_end]
        current_symbols[symbol] = current_symbols.get(symbol, 0) + 1

        while len(current_symbols) == symbol_count:
            # 更新最小片段长度和最小片段起始位置
            if window_end - window_start + 1 < window_len:
                window_len = window_end - window_start + 1
                min_start = window_start

            # 移除滑动窗口起始位置的符号,并更新符号计数
            symbol_at_start = target_str[window_start]
            current_symbols[symbol_at_start] -= 1
            if current_symbols[symbol_at_start] == 0:
                del current_symbols[symbol_at_start]
            window_start += 1

    return target_str[min_start:min_start+window_len]

target_str = input("请输入目标字符串:")
smallest_substring = find_smallest_substring(target_str)
print("包含所有符号的最小片段为:", smallest_substring)

这个算法的时间复杂度为O(n),其中n是目标字符串的长度。可以使用该算法找到一个包含目标字符串中所有符号的最小片段。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

JavaScript判断字符串是否包含某个片段几种方式

indexOf & lastIndexOf (可以用于数组) /* 使用indexOf判断,若返回-1则不包含,若包含则返回该片段第一次出现位置(lastIndexOf返回最后一次出现位置)。...*/ "doubleam我爱你".indexOf("doubleam"); search /* 使用search判断,若返回-1则不包含,若包含则返回该片段第一次出现位置。...原理:正则表达式 match()方法可在字符串内检索指定值,或找到一个或多个正则表达式匹配。 exec()方法用于检索字符串正则表达式匹配。返回一个数组,其中存放匹配结果。.../g);//return ["", ""]; ES6新增字符串扩展includes(可以用于数组) //@return boolean "doubleam我爱你我想你".includes("我爱你"...);//return true; 其他 也可以使用 'doubleam我爱你我想你'.split("我爱你"); 拆成数组通过长度来判断是否存在某个字符串片段,虽然不是很好用。

38710
  • 构成交替字符串需要最小交换次数

    题目 给你一个二进制字符串 s ,现需要将其转化为一个 交替字符串 。 请你计算并返回转化所需 最小 字符交换次数,如果无法完成转化,返回 -1 。...示例 2: 输入:s = "010" 输出:0 解释:字符串已经是交替字符串了,不需要交换。...解题 0, 1 个数差不能超过 1 个 个数相等的话,最终字符串 不是 0 开头就是 1 开头 不相等的话,多数字开头 依次比较,不相同位置就是需要调整 class Solution { public...else if((i&1)==0 && s[i]=='1') b++; } return min(n/2-a, n/2-b);//需要所有奇数位...CSDN博客地址 https://michael.blog.csdn.net/ 长按或扫码关注公众号(Michael阿明),一起加油、一起学习进步!

    35320

    Java 字符串包含_实现字符串复制

    1 问题描述 给定一长字符串A和一短字符串B。请问,如何最快地判断出短字符串B中所有字符是否都在长字符串A中?请编写一个判断函数实现此功能。 为简单起见,假设输入字符串包含小写英文字母。...(1)如果字符串A是”abcd”,字符串B是”bad”,答案是包含,因为字符串B中字母都在字符串A中,或者说B是A真子集。...(3)如果字符串A是”abcd”,字符串B是”aab”,答案是包含,因为字符串B中字母a包含字符串A中。...:A字符串包含B字符串 2.2 素数相乘法 思路如下: (1)按照从小到大顺序,用26个素数分别代替长字符串A中所有字母。...(2)遍历字符串A,求得A中所有字母对于素数乘积。 (3)遍历短字符串B,判断上一步得到乘积能否被B中字母对于素数整除。 (4)输出结果。

    1.2K30

    ABB TB852 包含所有服务和功能

    ABB TB852 包含所有服务和功能图片随着数字化转型席卷过程工业,许多公司都面临着协调创新和连续性挑战。乍一看,过程工业和信息技术似乎发展速度不同。...工厂运营商如何使用现代 IT 模型来优化他们流程,同时又不影响其运营高可用性、实时能力和冗余要求? ...NOA 补充了工厂现有的自动化结构,并提供了经典过程自动化和现代 IT 之间开放接口。数据可以从自动化金字塔中提取并安全地传输到其中,而不会危及已安装过程工厂可用性和安全性。...NOA 主要建立在现有的 OPC UA 标准之上,以便轻松地将快速变化 IT 组件集成到整个应用程序中。这对加工厂操作员意味着什么?...使用合适产品,您可以根据 NOA 扩展您工厂,以直接获得现代 IT 应用程序好处。Softing 基于我们在工业通信和 OPC UA 方面的丰富专业知识,提供多种满足过程工业特殊要求产品。

    19420

    给定一个字符串,找到包含字符串所有字符最短子串

    其思路是这样 首先遍历一次字符串,求出字符串不同字符数目 为每一个字符保存一个列表,记录该字符在字符串中出现索引 记录待求字符串首字母索引start(初始值为0),结束索引end(初始值为length...-1) 记录可能待求字符串首字母索引值为pStart(初始值为0) 重新遍历字符串,当前索引为index 更新没有遍历字符数目,更新当前字符对应索引列表。...如果pStart处字符对应列表长度大于1,则从索引列表中移出pStart,并将pStart加1,并重复该过程 如果index处字符是第一次出现,则将剩余字符数目减一 如果剩余字符数目为0时,且子字符串...getShortestSubString(String str) { if (str == null || str.length() <= 1) { return str; } // 记录目标字符串起始索引...int start = 0, end = str.length() - 1; // 记录目标字符串开始位置 int pStart = 0; Map<Character

    57710

    Objective-C 中接受符号

    不管怎么样样,点符号还是可以。 好了,这是曾一直是点符号坚定反对者。认为它掩盖了消息传递,并鼓励程序员通过链式点语法来违反 "得墨忒耳定律(Law of Demeter) "。...甚至将点符号描述为 Objective-C 代码一种气味。 因此,你可能会惊讶地发现,最近在代码中采用了点符号!事情是这样......既然不想使用点符号,那么调用 [[self prop] doSomething]; 需要简单地 [_prop doSomething]; KVO 链接属性 但后来 Eric Baker 制作了使用...与 KVO 相比,更喜欢使用通知主要原因是,喜欢使用单独方法来处理模型变化不同方面。而在 KVO 中,所有的观察都会转到一个方法,然后该方法必须根据变化类型来处理分派。...点符号:仍在关注得墨忒耳定律 仍然时刻关注着点符号数量,对得墨忒耳定律保持着敏感。连锁点仍然散发着不恰当亲密关系味道。

    10210
    领券