在字典中查找给定字符串的子序列中最长的单词（Google TechDevGuide）
https://techdevguide.withgoogle.com/paths/foundational/find-longth-word-in-dictionary-that-subsecence-of-givised-string#代码-挑战
“给定一个字符串S和一组单词D，找出D中最长的单词，它是S的子序列。如果可以从S中删除一些字符（可能为零）以形成W，而不对其余字符重新排序，则W是S的子序列。注意：D可以以任何格式出现（列表、哈希表、前缀树等）。例如，给定输入为S=”able“,”ale“,”apple“,”apple“,”bale“,”kangaroo“}，正确的输出将是”apple“”apple“
所以我的主要疑问是，在这一节中，指定了一个最优的方法O(n+l)，用于小字母表。在前面的方法O(N+L log N)中，作者构建了一个哈希表，映射字符串中的字符->排序索引
所以对于“abpple”，哈希表是：
a -> [0]
b -> [1]
p -> [2,3,4]
l -> [5]
e -> [6]
在小字母表的最优方法中，提到用稠密向量表示代替上述稀疏向量表示。
p -> [2, 2, 3, 4, -1, -1, -1, -1]
他们想代表什么？字符串S=“abppplee”确实有8个字符，但我不知道密集向量代表什么？这是一个错误还是我遗漏了什么？
谢谢你。
共有1个答案
据我所知，这个向量应该解决这个问题(y设置为字符p）
如果上一个匹配的字符位于索引X，而下一个匹配的字符是Y，那么这个匹配发生在哪里？
换句话说，如果您位于原始字符串中的索引i，则向量p[i]的元素告诉您字符串中最近的下一个字符p在哪里。
p -> [2, 2, 3, 4, -1, -1, -1, -1]
-
问题内容： 这个问题与Python类似-在字典中查找最长（最多单词）键-但我需要纯字符数。 输入示例： 输出： 问题答案： 替代方法，与@jamylak的解决方案一样快，并且使用更多的pythonic： 查看比较：
-
问题内容： 如何递归地查找字符串中最长的单词？ 编辑 说完了，谢谢大家。这是修改后的代码。 问题答案： 首先，让我们假设句子字符串参数没有任何前导或尾随空格。您可以通过调用trim（）来处理递归情况。 然后，我们需要定义两种情况，即基本情况和递归情况。 基本情况是找不到空格，即传入的句子只是一个单词。在这种情况下，只需返回句子即可。 在递归的情况下，我们将得到第一个单词，其余的则与您一样。在句子的
-
我知道如何使用动态规划来解决 <罢工> 大多数 给定两个字符串的最长公共子串或最长公共子串。然而，对于字符串Y的子串X的最长子序列问题，我很难找到一个解决方案。 查找字符串X的所有子序列并按长度desc排序； 遍历排序的子序列，如果当前子序列是Y的子字符串，则返回子序列。 它可以工作，但运行时间可能会很糟糕。假设X中的所有字符都是唯一的，那么有2^m个子群，其中m是X的长度，我认为检查一个字符串是
-
我需要找到字符串中最长的序列，并警告序列必须重复三次或更多次。例如，如果我的字符串是： fdwaw4helloworld vcdv1c3xcv3xcz1sda21f2sd1ahelloworld gafgfa4564534321fadghelloworld 然后我希望返回值“helloworld”。 我知道有几种方法可以做到这一点，但我面临的问题是，实际的字符串太大了，所以我真的在寻找一种能够及时
-
我如何在O(N**2)个时间内完成它？
-
问题是，我试图这么做，但我检查字符串长度的方法不起作用；我能做些什么来修复它？