• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            心如止水
            Je n'ai pas le temps
            posts - 400,comments - 130,trackbacks - 0

            給定一個僅包含小寫字母的英文單詞表,其中每個單詞最多包含50個字母。如果一張由一個詞或多個詞組成的表中,每個單詞(除了最后一個)都是排在它后面的單詞的前綴,則稱此表為一個詞鏈。例如下面的單詞組成了一個詞鏈:

            i

            int

            integer

            而下面的單詞不組成詞鏈:

            integer

            intern

                請在給定的單詞表中取出一些詞,組成最長的詞鏈。最長的詞鏈就是包含單詞數最多的詞鏈。

            數據保證給定的單詞表中,單詞互不相同,并且單詞按字典順序排列。單詞數最多10000

             

            先給出解題報告上的思路:

            用一個棧存儲當前的以第i個單詞結尾的最長詞鏈,第i+1個單詞加在棧的結尾(通過出棧保持棧所存儲的是一個詞鏈)。

                例如:

                i             i

                int          棧:  i int

                integer      棧:  i int interger

                intern       棧:  i int intern interger出棧)

                internet     棧:  i int intern internet

                可以證明,在第i個單詞插入后,當前在棧中的詞鏈就是包含第i個單詞的最長詞鏈。

                這樣由于每個單詞進棧出棧分別一次,所以算法的復雜度是O(n)

             

            我的思路比官方的解法稍微差了一點。遇到此類為題很容易想到用字典樹,程序我沒有寫。最多也只有50萬個結點,遍歷一次即可出解,應該可以AC

            posted on 2010-01-06 20:04 lee1r 閱讀(438) 評論(0)  編輯 收藏 引用 所屬分類: 題目分類:數據結構
            青草国产精品久久久久久| 免费国产99久久久香蕉| 亚洲国产日韩欧美综合久久| 精品久久久久久99人妻| 亚洲色欲久久久久综合网| 色诱久久久久综合网ywww | 久久99亚洲综合精品首页| 久久久久国产一级毛片高清板| 亚洲人成无码www久久久| 看久久久久久a级毛片| 久久精品国产72国产精福利| 久久久久99这里有精品10| 久久久国产精品网站| 午夜人妻久久久久久久久| 久久97久久97精品免视看| 亚洲va中文字幕无码久久| 亚洲第一永久AV网站久久精品男人的天堂AV | 久久久久久久久久久| 国产精品欧美久久久天天影视| 亚洲国产精品久久66| 99久久国产综合精品女同图片| 国产精品成人99久久久久| 久久久久久久久久久久中文字幕| 日本亚洲色大成网站WWW久久 | www.久久热| 国产精品久久久久久| 97久久超碰国产精品旧版| 综合人妻久久一区二区精品| AV无码久久久久不卡网站下载| 久久精品人人槡人妻人人玩AV| 日本国产精品久久| 性做久久久久久免费观看| 久久精品国产72国产精福利| 精品无码久久久久久久久久| 国产成人精品久久一区二区三区 | 99久久国产综合精品五月天喷水 | 久久天天躁狠狠躁夜夜躁2014 | 国内精品人妻无码久久久影院| 99久久国产精品免费一区二区| 日韩美女18网站久久精品| 亚洲精品午夜国产va久久|