Tag: 字符串

字符串哈希-字符串同构问题

摘要: 字符串同构问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 数据结构的同构问题是哈希表解决的一个基本问题,在给定数据结构的同构规则后,如何快速判断两个数据结构是否同构。 对于这种判定同构的

用字符串哈希解决经典问题:最长重复子串、最长公共子串

摘要: 可以用字符串哈希解决的经典问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 字符串哈希 中,我们学习了字符串哈希的原理和代码模板。 一些字符串中的经典问题用字符串哈希都可以解决,比

参考字符串哈希定义数组哈希(数组的同构)

摘要: 类似于字符串哈希的数组哈希,以及在数组同构中的应用。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 字符串哈希 中我们学习了字符串哈希的原理与代码模板。 对于长度为 m 的字符串 s

力扣940-不同的子序列

摘要: 不同的子序列 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个比较难的问题,算法的核心是动态规划,根据动态规划阶段的不同选取方式,有普通的一维线性DP,以及序列自动机两种做法。

序列自动机

摘要: 序列自动机原理、代码模板、应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们串讲一下序列自动机的原理和代码模板。然后解决力扣 392。 序列自动机在文章 词法分析-有限自动机 中,

深入Java字符串

摘要: 本文是关于 Java 中的字符串的要点总结。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings == 与 equals12345String str1 = String("abc");Stri

字符串哈希的哈希函数

摘要: 字符串哈希的哈希函数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 字符串哈希 中,我们探讨了字符串哈希,及其在字符串相关的经典问题中的应用。 字符串哈希是哈希中最常见的形式,在搜索

Trie单串多模式匹配,模式开头为统一特殊字符

$0 背景给定单串 s,n个模式串 p1, p2, …, pn。 其中 n 个模式串中,任意两个模式串都没有子串的关系,且都以一个特殊字符开头,模式的其它字符不会出现该特殊字符。 在 s 中找到所有匹配到这 n 个模式串的所有起始位置。 Trie用 n 个模式串建立一个 Trie。推进 i 的字符时,如果 s[i] 为特殊字符,则记录 j = i,并初始化 iter = root,之后尝试同时推进

小数转分数

摘要: 小数转分数的算法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们来看一下在数学算法中常见的小数转分数的问题。在编程中,除了整数以外,我们主要用的是小数,比如 float、double

双串线性DP,二维状态表示阶段

子序列匹配 392. 判断子序列 115. 不同的子序列 字符串模糊匹配 72. 编辑距离 712. 两个字符串的最小ASCII删除和 583. 两个字符串的删除操作 44. 通配符匹配 10. 正则表达式匹配 其它 97. 交错字符串 727. 最小窗口子序列 1458. 两个子序列的最大点积 $0 双串线性 DPdp[i][j]: i

力扣1316-不同的循环子字符串

字符串哈希 前缀哈希 string_view kmp $1 题目题目链接 1316. 不同的循环子字符串 题目描述给你一个字符串 text ,请你返回满足下述条件的 不同 非空子字符串的数目: 可以写成某个字符串与其自身相连接的形式(即,可以写为 a + a,其中 a 是某个字符串)。例如,abcabc 就是 abc 和它自身连接形成的。 提示:121 <= text.len

字符串哈希

摘要: 本文系统梳理了字符串哈希相关的要点,并通过字符串精确匹配问题给出代码模板。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们系统串讲一下字符串哈希算法。字符串哈希是一种哈希函数

【设计难题】力扣642-设计搜索自动补全系统

Trie $1 题目题目链接 642. 设计搜索自动补全系统 题目描述为搜索引擎设计一个搜索自动补全系统。用户会输入一条语句(最少包含一个字母,以特殊字符 ‘#’ 结尾)。除 ‘#’ 以外用户输入的每个字符,返回历史中热度前三并以当前输入部分为前缀的句子。下面是详细规则: 一条句子的热度定义为历史上用户输入这个句子的总次数。返回前三的句子需要按照热度从高到低排序(第一个是最热门的)。如果有

双向Trie

Trie基础 trie 01Trie 双向Trie 场景及方案 实现 745. 前缀和后缀搜索 算法1:双向 Trie 算法2:前缀Trie + 后缀Trie $0 双向Trie场景一个 Trie 可以预处理一批单词的所有前缀,或者所有后缀。此后可以快速进行与前缀匹配或者后缀匹配有关的查询。 有时需求会更近一步:即做一些前缀和后缀均需要匹配的查询。例如问前缀为 profix 同时

【多维分桶】力扣527-单词缩写

用哈希的方式对多属性分桶 维护桶内元素 排序 Trie $1 题目题目链接527. 单词缩写 题目描述给定一个由n个不重复非空字符串组成的数组,你需要按照以下规则为每个单词生成最小的缩写。 初始缩写由起始字母+省略字母的数量+结尾字母组成。若存在冲突,亦即多于一个单词有同样的缩写,则使用更长的前缀代替首字母,直到从单词到缩写的映射唯一。换而言之,最终的缩写必须只能映射到一个单词。若缩写并不

后缀数组

倍增法 基数排序: 非比较排序 后缀数组 1163. 按字典序排在最后的子串 基于后缀数组的字符串匹配 预处理 sa + 二分排名(sa的下标) 高度数组 $0 背景一个长度为 n 的字符串 s,共有 n 种后缀。现在想对这 n 个后缀排序,将排序结果保存在一个数组 sa 中。sa[i] := 排名为 i 的后缀的起始下标。 1234sa[i] := 排名为 i 的后缀的起

【DP难题】力扣466-统计重复个数

循环节优化暴力模拟 倍增优化DP 序列自动机 $1 题目题目链接466. 统计重复个数 题目描述由 n 个连接的字符串 s 组成字符串 S,记作 S = [s,n]。例如,[“abc”,3]=“abcabcabc”。 如果我们可以从 s2 中删除某些字符使其变为 s1,则称字符串 s1 可以从字符串 s2 获得。例如,根据定义,”abc” 可以从 “abdbec” 获得,但不能从 “acb

子序列匹配

摘要: 子序列匹配问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 字符串精确匹配 中我们学习了字符串精确匹配的问题,本文我们看一下子序列匹配问题,涉及到贪心、动态规划、序列自动机等算法。

【STL】字典序比较 lexicographical_compare

摘要: 本文介绍在 C++ STL 中的字典序比较方法 lexicographical_compare 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文介绍在 C++ STL 中的字典序比较方法

【C++17】string_view

摘要: 本文介绍 C++17 中的一个字符串相关的新特性 string_view,主要参考《C++17 STL Cookbook》$7-3 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文介绍 C

单词矩阵

【搜索难题】力扣425-单词方块 数据结构维护状态转移时所需的查询需求 剪枝手段: 剪枝 $1 题目题目链接面试题 17.25. 单词矩阵 题目描述给定一份单词的清单,设计一个算法,创建由字母组成的面积最大的矩形,其中每一行组成一个单词(自左向右),每一列也组成一个单词(自上而下)。不要求这些单词在清单里连续出现,但要求所有行等长,所有列等高。 如果有多个面积最大的矩形,输出任意一个均可。一

Trie题目汇总

Trie 基本功能的思想和实现 : 力扣208-Trie 208. 实现 Trie (前缀树) Trie 的插入,查找单词和前缀是否存在 211. 添加与搜索单词 - 数据结构设计 Trie 中的搜索 基于字典树的串上搜索 212. 单词搜索 II Trie + DFS 720. 词典中最长的单词 Trie + DFS 425. 单词方块 Trie + DFS 745. 前缀和后缀搜索

01Trie

摘要: 01Trie 的实现,附代码模板和应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 Trie 中我们了解了 Trie 的原理与实现。如果 Trie 的节点只含有 0, 1 这两种值

【搜索难题】力扣425-单词方块

DFS 数据结构维护状态转移 $1 题目题目链接425. 单词方块 题目描述给定一个单词集合 (没有重复),找出其中所有的 单词方块 。 一个单词序列形成了一个有效的单词方块的意思是指从第 k 行和第 k 列 (0 ≤ k < max(行数, 列数)) 来看都是相同的字符串。 例如,单词序列 [“ball”,”area”,”lead”,”lady”] 形成了一个单词方块,因为每个单词从水

字典序

386. 字典序排数 440. 字典序的第K小数字 1643. 第 K 条最小指令 1415. 长度为 n 的开心字符串中字典序第 k 小的字符串 $1 386. 字典序排数算法1: 字典树前序遍历字符集是 0123456789,将所有数字插入到字典树 按字典序输出所有数字,即对字典树前序遍历,将所有插入的数字输出,实现时与 N 叉树的前序遍历没有区别 123456789101112131

Redis中字符串的编码

摘要: Redis 中字符串的编码 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings Redis字符串类型内部编码 src/server.h src/sds.h src/object.c 相关题目

字符串精确匹配

摘要: 字符串精确匹配方法汇总 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们以 leetcode 第 28 题为模板题,总结一下字符串精确匹配的各种算法。 字符串精确匹配主流算法 暴力算

Trie

摘要: 经典的 Trie 的实现,附代码模板和应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们以力扣 208 作为模板题来学习一下 Trie 的建树,插入和查找。并形成代码模板。 模板题