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

查找没有字典或计数器的重复单词

在没有字典或计数器的情况下查找重复单词,可以采用双指针的方法。

双指针法的基本思路是,维护两个指针i和j,初始时i和j都指向字符串的起始位置。然后,让指针j依次向后遍历字符串的每个字符,同时检查指针j所指的字符是否在指针i之前的子串中出现过。如果出现过,说明找到了重复单词;如果没有出现过,则将指针j指向的字符加入到当前子串中,继续向后遍历。

以下是示例代码:

代码语言:txt
复制
def find_duplicate_words(s):
    i = 0
    j = 0
    duplicate_words = []
    current_word = ""

    while j < len(s):
        if s[j] != ' ':
            current_word += s[j]
        else:
            if current_word != "":
                if current_word in s[i:j]:
                    duplicate_words.append(current_word)
                else:
                    i = j + 1
                current_word = ""
        j += 1

    return duplicate_words

该代码会返回一个列表,包含所有重复出现的单词。

这种方法的时间复杂度是O(n^2),其中n是字符串的长度。每次检查是否重复时,需要遍历指针i和j之间的子串,最坏情况下需要遍历的子串长度为O(n),所以总的时间复杂度是O(n^2)。

这是一个比较简单的解决方案,如果需要更高效的方法,可以考虑使用字典或计数器来记录单词的出现次数。

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

相关·内容

【原创】python倒排索引之查找包含某主题单词文件

倒排索引(英语:Inverted index),也常被称为反向索引、置入档案反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中存储位置映射。...test2.txt"],"自然语言":["test1.txt"],"处理":["test1.txt"],"计算机":["test2.txt"],"视觉":["test2.txt"]} 建立倒排索引后,我们要想查找包含某些单词文件...open(file,'r',encoding='utf-8') as fp: word_list=fp.read().split(" ") #建立倒排索引,如果单词不在单词字典中...之后我们得到了关于文件索引次数字典,我们按次数从大到小排列,然后取前几个作为我们最后结果。...,不同单词间','隔开:") words = input().split(',') #获得文件名和文件名索引字典 files_name, files_dict = file_store

1.8K30

哈夫曼树、哈夫曼编码和字典

执行流程         字典树(Trie 树)是一种特殊树型数据结构,用于快速检索和查找字符串集合中单词前缀。它执行流程如下: (1)初始化字典树,创建一个根节点,根节点不包含任何值。...重复该过程,直到遍历完整个字符串。 (3)在字典树中查找指定单词前缀。从根节点开始,依次遍历待查找单词前缀中每个字符,如果存在当前字符对应节点,则向下遍历;否则,直接返回空。...(4)如果是查找单词,则需要判断查找最后一个节点是否为一个单词结束节点。如果是,则说明该单词存在于字典树中;否则,不存在。...(5)如果是查找前缀,则不需要判断最后一个节点是否为一个单词结束节点,只需要返回查找最后一个节点子树中所有单词即可。...字典优点是可以快速插入、查找和删除字符串集合中单词,时间复杂度为 O(m),其中 m 为单词长度。

38410
  • 搜索引擎背后数据结构和算法

    具体是这样做:维护一个中心计数器,每爬取到一个网页,就从计数器中拿一个号码,分配给这个网页,然后计数器加一。...只需要通过空格、标点符号等分隔符,将每个单词分割开来就可以了。 对于中文来说,分词就复杂太多了。介绍一种比较简单思路,基于字典和规则分词方法。 字典也叫词库,里面包含大量常用词语。...维护一个计数器,每当从网页文本信息中分割出一个新单词时候,就从计数器中取一个编号,分配给它,然后计数器加一。 在这个过程中,我们还需要使用散列表,记录已经编过号单词。...在对网页文本信息分词过程中,我们拿分割出来单词,先到散列表中查找,如果找到,那就直接使用已有的编号;如果没有找到,再去计数器中拿号码,并且将这个新单词以及编号添加到散列表中。...这个文件作用是,帮助我们快速地查找某个单词编号在倒排索引中存储位置,进而快速地从倒排索引中读取单词编号对应网页编号列表。 ?

    1.1K10

    使用 Python 程序实现摩斯密码翻译器

    加密 在加密情况下,我们一次一个地从单词中提取每个字符(如果不是空格),并将其与存储在我们选择任何数据结构中相应摩斯密码匹配(如果您使用 python 编码,字典可以变成在这种情况下非常有用) 将摩斯密码存储在一个变量中...我们重复这个过程,直到我们遍历整个字符串 解密 在解密情况下,我们首先在要解码字符串末尾添加一个空格(这将在后面解释)。 现在我们继续从字符串中提取字符,直到我们没有任何空间。...一旦我们得到一个空格,我们就会在提取字符序列(我们莫尔斯电码)中查找相应英语字符,并将其添加到将存储结果变量中。 请记住,跟踪空间是此解密过程中最重要部分。...键值可以从字典中访问,就像我们通过索引访问数组值一样,反之亦然。...' 'citext' -> '存储单个字符摩斯密码' 'i' -> '计算摩斯字符之间空格' 'message' -> '存储要编码解码字符串 ''' # 表示摩斯密码图字典 MORSE_CODE_DICT

    2.5K20

    使用 Python 程序实现摩斯密码翻译器「建议收藏」

    加密 在加密情况下,我们一次一个地从单词中提取每个字符(如果不是空格),并将其与存储在我们选择任何数据结构中相应摩斯密码匹配(如果您使用 python 编码,字典可以变成在这种情况下非常有用) 将摩斯密码存储在一个变量中...我们重复这个过程,直到我们遍历整个字符串 解密 在解密情况下,我们首先在要解码字符串末尾添加一个空格(这将在后面解释)。 现在我们继续从字符串中提取字符,直到我们没有任何空间。...一旦我们得到一个空格,我们就会在提取字符序列(我们莫尔斯电码)中查找相应英语字符,并将其添加到将存储结果变量中。 请记住,跟踪空间是此解密过程中最重要部分。...键值可以从字典中访问,就像我们通过索引访问数组值一样,反之亦然。...' 'citext' -> '存储单个字符摩斯密码' 'i' -> '计算摩斯字符之间空格' 'message' -> '存储要编码解码字符串 ''' # 表示摩斯密码图字典 MORSE_CODE_DICT

    1.3K20

    20个值得学习 Python 技巧

    str1="aabbccccdddd" set1=set(str1) new_str=''.join(set1) print(new_str) 4 重复打印字符串列表 下面的代码中,对字符串列表使用...Python 计数器跟踪容器中每个元素频数, Counter()返回一个字典,元素作为键,频数作为值。 另外使用 most_common()函数来获取列表中 出现次数最多元素。...Counter(list1) print(count) print(count['b']) print(count.most_common(1)) 11 判断两个字符串是否为异序词 异序词是通过重新排列不同单词短语字母而形成单词短语...,添加 else 语句,会在 try 块中没有引发异常情况下运行。...下面脚本中,两个字典被合并。在相交情况下,使用第二个字典值。

    90820

    20个值得学习 Python 技巧

    str1="aabbccccdddd" set1=set(str1) new_str=''.join(set1) print(new_str) 4 重复打印字符串列表 下面的代码中,对字符串列表使用...Python 计数器跟踪容器中每个元素频数, Counter()返回一个字典,元素作为键,频数作为值。 另外使用 most_common()函数来获取列表中 出现次数最多元素。...Counter(list1) print(count) print(count['b']) print(count.most_common(1)) 11 判断两个字符串是否为异序词 异序词是通过重新排列不同单词短语字母而形成单词短语...,添加 else 语句,会在 try 块中没有引发异常情况下运行。...下面脚本中,两个字典被合并。在相交情况下,使用第二个字典值。

    70710

    如何在一场面试中展现你对Pythoncoding能力?

    return random.choice(all_words) 你应该重复调用get_random_word()以获取1000个随机单词,然后返回包含每个唯一单词数据结构。...这意味着随着单词数量增加,查找次数呈二次方式增长。换句话说,时间复杂度在O(N^2)量级上增长。...使用.get()和.setdefault()在字典中定义默认值 最常见编程任务之一涉及添加,修改检索可能在字典中或可能不在字典项。...如果没有,则将它们添加到字典中,并将空列表作为默认值。然后将实际成绩附加到该学生成绩列表中。...使用collections.Counter计算Hashable对象 假如你有一长串没有标点符号大写字母单词,你想要计算每个单词出现次数。

    1.2K30

    如何在一场面试中展现你对Pythoncoding能力?

    return random.choice(all_words) 你应该重复调用get_random_word()以获取1000个随机单词,然后返回包含每个唯一单词数据结构。...这意味着随着单词数量增加,查找次数呈二次方式增长。换句话说,时间复杂度在O(N^2)量级上增长。...使用.get()和.setdefault()在字典中定义默认值 最常见编程任务之一涉及添加,修改检索可能在字典中或可能不在字典项。...如果没有,则将它们添加到字典中,并将空列表作为默认值。然后将实际成绩附加到该学生成绩列表中。...使用collections.Counter计算Hashable对象 假如你有一长串没有标点符号大写字母单词,你想要计算每个单词出现次数。

    1.4K40

    如何在一场面试中展现你对Pythoncoding能力?| 技术头条

    return random.choice(all_words) 你应该重复调用get_random_word()以获取1000个随机单词,然后返回包含每个唯一单词数据结构。...这意味着随着单词数量增加,查找次数呈二次方式增长。换句话说,时间复杂度在O(N^2)量级上增长。...使用.get()和.setdefault()在字典中定义默认值 最常见编程任务之一涉及添加,修改检索可能在字典中或可能不在字典项。...如果没有,则将它们添加到字典中,并将空列表作为默认值。然后将实际成绩附加到该学生成绩列表中。...使用collections.Counter计算Hashable对象 假如你有一长串没有标点符号大写字母单词,你想要计算每个单词出现次数。

    1.1K30

    Python基础知识点梳理

    注释 类型 语法 单行注释 以 # 开头,编程规范建议#后面跟一个空格 多行注释 用一对连续三个引号,单引号或者双引号均可("""/’’’) 行与缩进 python与其他语言明显区别是没有大括号...循环是python中常见循环,用于让执行代码按照指定次数重复执行,语法如下: 初始条件设置,通常是计数器 while 条件(判断计数器是否达到目标次数): 条件满足时候执行代码...处理条件(计数器 + 1) 1 2 3 4 5 for循环 for循环可以方便地遍历列表,元组,字典等数据类型,比如遍历一个列表代码片段如下: nameList = ["zhangsan", "lisi...每个单词首字母大写)则返回True 05 str.isupper() 如果 string 所有区分大小写字符都是大写,则返回True 06 str.islower() 如果...11 大小写 str.swapcase() 翻转字符串大小写 字符串查找和替换: 序号 方法 说明 01 str.count(str1, beg=0, end=

    1.4K10

    字典树简介

    文章目录 1.简介 2.性质 3.示例 4.用途 5.操作 插入 删除 查找 6.实现示例 树结构 创建树 查询单词前缀数量 在主函数中测试 7.小结 参考文献 1.简介 字典树(Trie)又名前缀树单词查找树...4.用途 字典树可以被广泛应用于字符串检索和匹配问题,比如: 实现字符串自动补全和纠错功能。 在搜索引擎中实现关键词提示。 统计和查找文本中特定单词短语出现次数。...如果该节点不是一个字符串节点,且其没有其他子节点,可以将该节点从其父节点子节点列表中删除,并继续向上遍历父节点。 重复步骤3和4,直到所有需要删除节点都被删除或者遍历到根节点为止。...需要注意是,字典删除操作有可能会导致一些无用节点残留在树中,因此为了维持字典空间效率,我们可以在插入和删除操作时对树进行压缩,即如果一个节点没有其他子节点,并且其父节点也没有其他子节点,则将该节点和其父节点合并成一个节点...+1 root.count++; } 查询单词前缀数量 //查找单词是否存在,如果存在返回数量,不存在返回-1 public static int search(TrieNode root

    86230

    剑指Offer——Trie树(字典树)

    大家好,又见面了,我是你们朋友全栈君。 剑指Offer——Trie树(字典树) Trie树 Trie树,即字典树,又称单词查找键树,是一种树形结构,是一种哈希树变种。...4、1000万字符串,其中有些是重复,需要把重复全部去掉,保留没有重复字符串。请怎么设计和实现?...举例 下面以字典构建与单词查找为例。...(只有小写字母组成,不会有重复单词出现),现在老师要他统计 * 出以某个字符串为前缀单词数量(单词本身也是自己前缀). */ String[] strs = { "banana", "band...(只有小写字母组成,不会有重复单词出现),现在老师要他统计 * 出以某个字符串为前缀单词数量(单词本身也是自己前缀). */ String[] strs = { "banana", "band

    88710

    27个Linux文档编辑命令

    但ed文本编辑器对于编辑大文件对于在shell脚本程序中进行文本编辑很有用。 Linux egrep命令 Linux egrep命令用于在文件内查找指定字符串。...若在检查文件中找到字典没有的词汇,ispell会建议使用词汇,或是让你将新词汇加入个人字典。 Linux jed命令 Linux jed命令用于编辑文本文件。...Linux look命令 Linux look命令用于查询单词。 look指令用于英文单字查询。您仅需给予它欲查询字首字符串,它会显示所有开头字符串符合该条件单字。...Linux expr命令 expr命令是一个手工命令行计数器,用于在UNIX/LINUX下求表达式变量值,一般用于整数值,也可用于字符串。...Linux uniq命令 Linux uniq命令用于检查及删除文本文件中重复出现行列。 uniq可检查文本文件中重复出现行列。 Linux wc命令 Linux wc命令用于计算字数。

    2.3K60

    27个Linux文档编辑命令

    但ed文本编辑器对于编辑大文件对于在shell脚本程序中进行文本编辑很有用。 Linux egrep命令 Linux egrep命令用于在文件内查找指定字符串。...若在检查文件中找到字典没有的词汇,ispell会建议使用词汇,或是让你将新词汇加入个人字典。 Linux jed命令 Linux jed命令用于编辑文本文件。...Linux look命令 Linux look命令用于查询单词。 look指令用于英文单字查询。您仅需给予它欲查询字首字符串,它会显示所有开头字符串符合该条件单字。...Linux expr命令 expr命令是一个手工命令行计数器,用于在UNIX/LINUX下求表达式变量值,一般用于整数值,也可用于字符串。...Linux uniq命令 Linux uniq命令用于检查及删除文本文件中重复出现行列。 uniq可检查文本文件中重复出现行列。 Linux wc命令 Linux wc命令用于计算字数。

    3K60

    用于日常编程问题 10 个 Python 代码片段

    dlroW ,olleH 此代码使用 Python 切片功能,步长为 -1,以反转输入字符串中字符序列。 查找列表中最常用元素 有时,您必须标识列表中最常用元素。...计算数阶乘 数 n 阶乘(表示为 n!)是所有正可积性小于上升到 n 项。...检查数字是否为质数 素数是大于 1 数,除了 1 和自身之外没有除数。...合并两个词典 合并两个词典是一项常见任务,尤其是在使用配置设置时。您将能够使用 update() 策略 {**dict1, **dict2} 语言结构组合两个词典。...如果存在重复键,dict2 中值将覆盖字典 1 中值。 从字符串中删除标点符号 处理文本数据时,可能需要从字符串中删除标点符号。

    28520

    华为机试HJ27-查找兄弟单词-C++实现

    HJ27 查找兄弟单词 题目描述: 描述 定义一个单词“兄弟单词”为:交换该单词字母顺序(注:可以交换任意次), 而不添加、删除、修改原有的字母就能生成单词。...现在给定你 n 个单词,另外再给你一个单词 x ,让你寻找 x 兄弟单词里,按字典序排列后第 k 个单词是什么? 注意:字典中可能有重复单词。...数据范围:1≤n≤1000 ,输入字符串长度满足 1≤len(str)≤10 , 1≤k<n 输入描述: 输入只有一行。 先输入字典单词个数n,再输入n个单词作为字典单词。...然后输入一个单词x 最后后输入一个整数k 输出描述: 第一行输出查找到x兄弟单词个数m 第二行输出查找按照字典顺序排序后第k个兄弟单词没有符合第k个的话则不用输出。...cab cba bca,所以输出3 经字典序排列后,变为bca cab cba,所以第1个字典序兄弟单词为bca 解题思路: 这是一道字符串题目。

    45430

    常用图像分类功能包

    为了能够有效地识别位置,我们需要提取表征图像特征,之后将相同特征分成一组,并搜索相似的图像。当然位置识别也可以应用于其他程序,例如在图像恢复我们也需要查找相似图像。...获得特征向量后,我们通过聚类算法得到这些特征向量聚类中心。将这些聚类中心组合在一起,形成字典。...对于图像中每个SIFT功能,我们都可以在字典中找到最相似的视觉单词。这样,我们可以计算一个k维直方图,它表示字典中图像SIFT特征。 ?...将视觉单词应用于图像检索 当我们使用进行图像搜索时,将会查看哪些视觉单词出现在该图像中。对于每个出现单词,我们检查哪些其他图像具有相同单词。对于有相同特征向量图像,我们在数组计数器中添加一个。...该数组是一个列表,其中每个图像都有一个包含计数器变量变量。最后,我们将数组中计数器值最高图像作为该图像匹配项。 但是,图像中每个功能仍需要与词汇表中所有可视单词进行比较。

    46320

    添加与搜索单词 - 数据结构设计

    二 题目描述与示例 2.1 描述 leetcode题目描述: 请你设计一个数据结构,支持 添加新单词查找字符串是否与任何先前添加字符串匹配 。...Trie树可以用O(∣S∣) 时间复杂度完成向字典树插入元素 和 查询字符串是否在树中两个操作,其中 ∣S∣ 是插入字符串查询前缀长度: 2.3.4 Trie与哈希表对比 最坏情况时间复杂度比hash...四 实现 4.1 关键问题 重点在于查找方法,对于搜索单词,从字典根结点开始搜索。由于待搜索单词可能包含点号,因此在搜索过程中需要考虑点号处理。...,由于点号可以表示任何字母,因此需要对当前结点所有非空子结点继续搜索下一个字符。 重复上述步骤,直到返回false 搜索完给定单词最后一个字符。...O(1),添加单词为O(∣S∣),搜索单词为 O(∣Σ∣|S∣),其中∣S∣ 是每次添加搜索单词长度,Σ 是字符集,这道题中字符集为全部小写英语字母,∣Σ∣=26。

    61030
    领券