连续添加char以获取字典中最长的单词（连续添加char以获取字典中最长的单词是什么）

25-04-11 7

对于想了解连续添加char以获取字典中最长的单词的读者，本文将是一篇不可错过的文章，我们将详细介绍连续添加char以获取字典中最长的单词是什么，并且为您提供关于2021-10-15：单词拆分。给定一个

对于想了解连续添加char以获取字典中最长的单词的读者，本文将是一篇不可错过的文章，我们将详细介绍连续添加char以获取字典中最长的单词是什么，并且为您提供关于2021-10-15：单词拆分。给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明：拆分时可以重复使用字典中的单词。你、c++ 获取字符串中最长的回文子串、C＃-字典-如何获取字典中特定类的最大值？、Haskell – 找到文本中最长的单词的有价值信息。

本文目录一览：

连续添加char以获取字典中最长的单词（连续添加char以获取字典中最长的单词是什么）
2021-10-15：单词拆分。给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明：拆分时可以重复使用字典中的单词。你
c++ 获取字符串中最长的回文子串
C＃-字典-如何获取字典中特定类的最大值？
Haskell – 找到文本中最长的单词

连续添加char以获取字典中最长的单词（连续添加char以获取字典中最长的单词是什么）

给定单词词典和首字母。通过在单词中连续添加一个字符，可以在字典中找到最长的单词。在任何给定的情况下，该单词在词典中应为有效单词。

例如：a-> at-> cat-> cart-> chart…。

答案1

小编典典

蛮力方法是尝试使用深度优先搜索将字母添加到每个可用索引中。

因此，从“ a”开始，您可以在两个地方添加新字母。在“ a”的前面或后面，由下面的点表示。

.a.

如果添加“ t”，则现在有三个位置。

.a.t.

您可以尝试将所有26个字母添加到每个可用位置。在这种情况下，字典可以是简单的哈希表。如果在中间添加“ z”，则会得到“
azt”，它不会出现在哈希表中，因此不会在搜索中沿该路径继续。

编辑：尼克·约翰逊的图让我很好奇所有最大路径的图是什么样子。这是一张大图（1.6 MB）：

http://www.michaelfogleman.com/static/images/word_graph.png

编辑：这是一个Python实现。暴力破解方法实际上需要一段合理的时间（几秒钟，取决于起始字母）。

import heapqletters = ''abcdefghijklmnopqrstuvwxyz''def search(words, word, path):    path.append(word)    yield tuple(path)    for i in xrange(len(word)+1):        before, after = word[:i], word[i:]        for c in letters:            new_word = ''%s%s%s'' % (before, c, after)            if new_word in words:                for new_path in search(words, new_word, path):                    yield new_path    path.pop()def load(path):    result = set()    with open(path, ''r'') as f:        for line in f:            word = line.lower().strip()            result.add(word)    return resultdef find_top(paths, n):    gen = ((len(x), x) for x in paths)    return heapq.nlargest(n, gen)if __name__ == ''__main__'':    words = load(''TWL06.txt'')    gen = search(words, ''b'', [])    top = find_top(gen, 10)    for path in top:        print path

当然，答案中会有很多纽带。这将打印出前N个结果，以最后一个单词的长度衡量。

使用TWL06拼字字典输出首字母’a’。

(10, (''a'', ''ta'', ''tap'', ''tape'', ''taped'', ''tamped'', ''stamped'', ''stampede'', ''stampedes'', ''stampeders''))(10, (''a'', ''ta'', ''tap'', ''tape'', ''taped'', ''tamped'', ''stamped'', ''stampede'', ''stampeder'', ''stampeders''))(10, (''a'', ''ta'', ''tan'', ''tang'', ''stang'', ''strang'', ''strange'', ''strangle'', ''strangles'', ''stranglers''))(10, (''a'', ''ta'', ''tan'', ''tang'', ''stang'', ''strang'', ''strange'', ''strangle'', ''strangler'', ''stranglers''))(10, (''a'', ''ta'', ''tan'', ''tang'', ''stang'', ''strang'', ''strange'', ''stranges'', ''strangles'', ''stranglers''))(10, (''a'', ''ta'', ''tan'', ''tang'', ''stang'', ''strang'', ''strange'', ''stranges'', ''strangers'', ''stranglers''))(10, (''a'', ''ta'', ''tan'', ''tang'', ''stang'', ''strang'', ''strange'', ''stranges'', ''strangers'', ''estrangers''))(10, (''a'', ''ta'', ''tan'', ''tang'', ''stang'', ''strang'', ''strange'', ''stranges'', ''estranges'', ''estrangers''))(10, (''a'', ''ta'', ''tan'', ''tang'', ''stang'', ''strang'', ''strange'', ''stranger'', ''strangler'', ''stranglers''))(10, (''a'', ''ta'', ''tan'', ''tang'', ''stang'', ''strang'', ''strange'', ''stranger'', ''strangers'', ''stranglers''))

这是每个起始字母的结果。当然，例外是字典中不必包含单个起始字母。可以用它组成一些2个字母的单词。

(10, (''a'', ''ta'', ''tap'', ''tape'', ''taped'', ''tamped'', ''stamped'', ''stampede'', ''stampedes'', ''stampeders''))(9, (''b'', ''bo'', ''bos'', ''bods'', ''bodes'', ''bodies'', ''boodies'', ''bloodies'', ''bloodiest''))(1, (''c'',))(10, (''d'', ''od'', ''cod'', ''coed'', ''coped'', ''comped'', ''compted'', ''competed'', ''completed'', ''complected''))(10, (''e'', ''re'', ''rue'', ''ruse'', ''ruses'', ''rouses'', ''arouses'', ''carouses'', ''carousels'', ''carrousels''))(9, (''f'', ''fe'', ''foe'', ''fore'', ''forge'', ''forges'', ''forgoes'', ''forgoers'', ''foregoers''))(10, (''g'', ''ag'', ''tag'', ''tang'', ''stang'', ''strang'', ''strange'', ''strangle'', ''strangles'', ''stranglers''))(9, (''h'', ''sh'', ''she'', ''shes'', ''ashes'', ''sashes'', ''slashes'', ''splashes'', ''splashers''))(11, (''i'', ''pi'', ''pin'', ''ping'', ''oping'', ''coping'', ''comping'', ''compting'', ''competing'', ''completing'', ''complecting''))(7, (''j'', ''jo'', ''joy'', ''joky'', ''jokey'', ''jockey'', ''jockeys''))(9, (''k'', ''ki'', ''kin'', ''akin'', ''takin'', ''takins'', ''takings'', ''talkings'', ''stalkings''))(10, (''l'', ''la'', ''las'', ''lass'', ''lassi'', ''lassis'', ''lassies'', ''glassies'', ''glassines'', ''glassiness''))(10, (''m'', ''ma'', ''mas'', ''mars'', ''maras'', ''madras'', ''madrasa'', ''madrassa'', ''madrassas'', ''madrassahs''))(11, (''n'', ''in'', ''pin'', ''ping'', ''oping'', ''coping'', ''comping'', ''compting'', ''competing'', ''completing'', ''complecting''))(10, (''o'', ''os'', ''ose'', ''rose'', ''rouse'', ''rouses'', ''arouses'', ''carouses'', ''carousels'', ''carrousels''))(11, (''p'', ''pi'', ''pin'', ''ping'', ''oping'', ''coping'', ''comping'', ''compting'', ''competing'', ''completing'', ''complecting''))(3, (''q'', ''qi'', ''qis''))(10, (''r'', ''re'', ''rue'', ''ruse'', ''ruses'', ''rouses'', ''arouses'', ''carouses'', ''carousels'', ''carrousels''))(10, (''s'', ''us'', ''use'', ''uses'', ''ruses'', ''rouses'', ''arouses'', ''carouses'', ''carousels'', ''carrousels''))(10, (''t'', ''ti'', ''tin'', ''ting'', ''sting'', ''sating'', ''stating'', ''estating'', ''restating'', ''restarting''))(10, (''u'', ''us'', ''use'', ''uses'', ''ruses'', ''rouses'', ''arouses'', ''carouses'', ''carousels'', ''carrousels''))(1, (''v'',))(9, (''w'', ''we'', ''wae'', ''wake'', ''wakes'', ''wackes'', ''wackest'', ''wackiest'', ''whackiest''))(8, (''x'', ''ax'', ''max'', ''maxi'', ''maxim'', ''maxima'', ''maximal'', ''maximals''))(8, (''y'', ''ye'', ''tye'', ''stye'', ''styed'', ''stayed'', ''strayed'', ''estrayed''))(8, (''z'', ''za'', ''zoa'', ''zona'', ''zonae'', ''zonate'', ''zonated'', ''ozonated''))

2021-10-15：单词拆分。给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明：拆分时可以重复使用字典中的单词。你

2021-10-15：单词拆分。给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明：拆分时可以重复使用字典中的单词。你

2021-10-15：单词拆分。给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明：拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。力扣139。

福大大答案2021-10-15：

自然智慧。从左往右尝试，用前缀树。如果没路了，就不需要试了。
时间复杂度：O(N)。
额外空间复杂度：O(N)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
   
    if true {
   
        s := "leetcode"
        wordDict := []string{
   "leet", "code"}
        ret := wordBreak1(s, wordDict)
        fmt.Println(ret)
    }
    if true {
   
        s := "leetcode"
        wordDict := []string{
   "leet", "code"}
        ret := wordBreak2(s, wordDict)
        fmt.Println(ret)
    }
}

type Node struct {
   
    end   bool
    nexts []*Node
}

func NewNode() *Node {
   
    res := &Node{
   }
    res.end = false
    res.nexts = make([]*Node, 26)
    return res
}

func wordBreak1(s string, wordDict []string) bool {
   
    root := NewNode()
    for _, str := range wordDict {
   
        chs := []byte(str)
        node := root
        index := 0
        for i := 0; i < len(chs); i++ {
   
            index = int(chs[i] - ''a'')
            if node.nexts[index] == nil {
   
                node.nexts[index] = NewNode()
            }
            node = node.nexts[index]
        }
        node.end = true
    }
    str := []byte(s)
    N := len(str)
    dp := make([]bool, N+1)
    dp[N] = true // dp[i] word[i.....] 能不能被分解
    // dp[N] word[N...] -> "" 能不能够被分解
    // dp[i] ... dp[i+1
    for i := N - 1; i >= 0; i-- {
   
        // i
        // word[i....] 能不能够被分解
        // i..i i+1....
        // i..i+1 i+2...
        cur := root
        for end := i; end < N; end++ {
   
            cur = cur.nexts[str[end]-''a'']
            if cur == nil {
   
                break
            }
            // 有路！
            if cur.end {
   
                // i...end 真的是一个有效的前缀串 end+1.... 能不能被分解
                dp[i] = dp[i] || dp[end+1]

            }
            if dp[i] {
   
                break
            }
        }
    }
    return dp[0]
}

func wordBreak2(s string, wordDict []string) int {
   
    root := NewNode()
    for _, str := range wordDict {
   
        chs := []byte(str)
        node := root
        index := 0
        for i := 0; i < len(chs); i++ {
   
            index = int(chs[i] - ''a'')
            if node.nexts[index] == nil {
   
                node.nexts[index] = NewNode()
            }
            node = node.nexts[index]
        }
        node.end = true
    }
    str := []byte(s)
    N := len(str)
    dp := make([]int, N+1)
    dp[N] = 1
    for i := N - 1; i >= 0; i-- {
   
        cur := root
        for end := i; end < N; end++ {
   
            cur = cur.nexts[str[end]-''a'']
            if cur == nil {
   
                break
            }
            if cur.end {
   
                dp[i] += dp[end+1]
            }
        }
    }
    return dp[0]
}

执行结果如下：

左神java代码

c++ 获取字符串中最长的回文子串

#include <vector>
#include <iostream>
#include <string>
using namespace std;
string Manacher(string s) {

    // 插入特殊符号“#”
    string t = "$#";
    for (int i = 0; i < s.size(); ++i) {
        t += s[i];
        t += "#";
    }

    // 初始化变量
    vector<int> p(t.size(), 0);
    int mx = 0, id = 0, resLen = 0, resCenter = 0;

    //循环t.size()-1次
    for (int i = 1; i < t.size(); ++i) {

        // p[i]:表示以 t[i] 字符为中心的回文子串的半径
        // i < mx 的含义:证明 i 在 当前id 对应子回文串的范围之内
        p[i] = i<mx ? min(p[2 * id - i], mx - i) : 1;

        //从字符串中点向两端扩展,直到不能再扩展
        while (t[i + p[i]] == t[i - p[i]]){
            ++p[i];
        }

        //mx:当前已经处理的回文子串所达最靠后的终点
        //id:终点最靠后的回文子串的中心字符下标
        if (mx < i + p[i]) {
            mx = i + p[i];
            id = i;
        }

        //结果
        //回文字符串最大长度reslen
        //回文字符串的中心位置resCenter
        if (resLen < p[i]) {
            resLen = p[i];
            resCenter = i;
        }
    }

    //例子： "noon"，中间的 ''#'' 在字符串 "$#n#o#o#n#" 中的位置是5，半径也是5，
    //字符串的长度（半径减一）：4，起始位置（中间位置减去半径再除以2）：0

    //结论：最长子串的长度是半径resLen减1，起始位置是中间位置resCenter减去半径resLen再除以2。
    return s.substr((resCenter - resLen) / 2, resLen - 1);
}

//主程序
int main() {
    string s = "aawaw";
    cout << Manacher(s) << endl;
}

参考：

https://www.jianshu.com/p/c82cada7e5b0
https://www.cnblogs.com/grandyang/p/4475985.html
https://www.jianshu.com/p/7dacc9a3c9a0

C＃-字典-如何获取字典中特定类的最大值？

要获得最多LineInfo个lineDistance，可以使用Values集合。由于标准LINQ中没有MaxBy，因此您可以使用Aggregate达到类似的效果：

var max = lines.Values
    .Aggregate((acc,curr) => acc.lineDistance > curr.lineDistance ? acc: curr);

如果我对问题的理解正确，则Linq中的Max有一个重载，它允许您指定一个属性，即：

double max = lines.Max(x => x.Value.lineDistance);

修改

如果您需要该对象，则@ itsme86解决方案最有效：

LineInfo maxLineInfo = lines.Values.OrderByDescending(line => line.lineDistance).First();

Haskell – 找到文本中最长的单词

我有一个问题是写一个函数来找到文本中最长的单词.

输入：包含大量单词的字符串.例如：“我是一个年轻人,我有一个大房子.”

结果将是5,因为文本中最长的单词有5个字母(年轻和房子).

我刚刚开始学习Haskell.我试过了：

import Char
import List

maxord' (str:strs) m n = 
    if isAlpha str == True
    then maxord'(strs m+1 n)
else    if m >= n
        then maxord'(strs 0 m)
    else    maxord'(strs 0 n)

maxord (str:strs) = maxord' (str:strs) 0 0

我想返回n作为结果,但我不知道该怎么做,似乎代码也有问题.

有帮助吗？谢谢

解决方法

这里有几个问题.让我们从语法开始.

您的其他部分应缩进与它们所属的相同或更多,例如,如下所示：

if ...
then ...
else if ...
     then ...
     else ...

接下来,您的功能应用程序与许多其他语言不同,在Haskell中,括号仅用于分组和元组.由于函数应用程序在Haskell中如此常见,我们使用最轻量级的语法,即空格.因此,要将函数maxord’应用于参数strs,m 1和n,我们将写入maxord’strs(m 1)n.请注意,由于函数应用程序具有最高优先级,我们必须在m 1附近添加括号,否则它将被解释为(maxord’strs m)(1 n).

这就是语法.下一个问题是语义问题,即你有没有基本情况的递归.使用模式(str：strs),您已经指定了在剩下一些字符时要执行的操作,但是当您到达字符串末尾时没有指定要执行的操作.在这种情况下,我们想要返回n,所以我们为此添加一个案例.

maxord' [] m n = n

因此,固定的maxord’

maxord' [] m n = n
maxord' (str:strs) m n = 
    if isAlpha str == True
    then maxord' strs (m+1) n
    else if m >= n
         then maxord' strs 0 m
         else maxord' strs 0 n

但请注意,此解决方案并不是非常惯用.它使用显式递归,如果表达式而不是保护,将布尔值与True进行比较,并且具有非常迫切的感觉.一个更惯用的解决方案就是这样.

maxord = maximum . map length . words

这是一个简单的函数链,其中单词将输入分成单词列表,映射长度用其长度替换每个单词,最大值返回这些长度的最大值.

虽然,请注意它与您的代码不完全相同,因为在分割输入时,单词function使用稍微不同的标准.

关于连续添加char以获取字典中最长的单词和连续添加char以获取字典中最长的单词是什么的介绍现已完结，谢谢您的耐心阅读，如果想了解更多关于2021-10-15：单词拆分。给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明：拆分时可以重复使用字典中的单词。你、c++ 获取字符串中最长的回文子串、C＃-字典-如何获取字典中特定类的最大值？、Haskell – 找到文本中最长的单词的相关知识，请在本站寻找。

本文标签：