<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    小明思考

    Just a software engineer
    posts - 124, comments - 36, trackbacks - 0, articles - 0
      BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

    子序列計數

    Posted on 2013-04-26 23:33 小明 閱讀(2033) 評論(1)  編輯  收藏 所屬分類: 數據結構和算法
    問題給定兩個字符串S和T,計算S的子序列為T的個數。

    這里的字符串的子序列指的是刪除字符串的幾個字符(也可以不刪)而得到的新的字符串,但是不能改變字符的相對位置。

    比如“ACE”是“ABCDE”的子序列,但是“AEC”就不是。

    如果S=“rabbbit” T=“rabit”,有3種不同的子序列為T的構成方法,那么結果應該返回3。

    分析:

    解法一:遞歸
    直覺的解法是使用遞歸,先在S中找到T的第一個字符,然后遞歸查找在剩余的S查找剩余的T(除去首字符)。
    如果T的長度為1,只需要計算S中一共有幾個T就可以了。
    代碼如下,非常簡潔,但是效率不高:

    public int numDistinct(String S, String T) {
            int ls = S.length();
            int lt = T.length();
            if(ls<lt){
                return 0;
            }
            
            char[] cs = S.toCharArray();
            char t0 = T.charAt(0);
            String T1 = T.substring(1);
            
            int result = 0;
            for(int i=0;i<ls;++i){
                if(cs[i]==t0){
                    if(lt>1){
                        result += numDistinct(S.substring(i+1),T1);
                    }
                    else{
                        ++result;
                    }
                }    
            }
            return result;
        }

    解法二,
    為了提高效率,很自然的想法是使用動態規劃,記錄中間狀態,從而避免重復計數。

    狀態轉移方程如下,計D(m,n)為S的子串(0..m)中子序列為T(0..n)的個數。

    那么D(m,n) = D(m-1,n) if S(m)<>T(n)
                     = D(m-1,n)+D(m-1,n-1) if (S(m)=T(n) and n>0)
                     = D(m-1,n)+1 if(S(m)=T(0) and n=0)

    代碼如下:復雜度為O(mn) m,n為S和T的長度

    public int numDistinct(String S, String T) {
            int ls = S.length();
            int lt = T.length();
            if(ls<lt){
                return 0;
            }
            
            int[][] memo = new int[ls][lt];
            char[] cs = S.toCharArray();
            char[] ct = T.toCharArray();
            
            memo[0] = new int[lt];
            memo[0][0]= (cs[0]==ct[0])?1:0;
            
            for(int i=1;i<ls;++i){
                int[] mprev = memo[i-1];
                int[] m = memo[i] = new int[lt];
                char s = cs[i];
                for(int j=0;j<lt;++j){
                    char t = ct[j];
                    m[j] = mprev[j];
                    if(s==t){
                        m[j] += ((j==0)?1:mprev[j-1]);
                    }
                }
            }
            return memo[ls-1][lt-1];
        }

    評論

    # re: 子序列計數  回復  更多評論   

    2013-06-12 23:56 by 初學者:阿古

    7.字符串String str = “ABCDEABCDABC”;定義一個方法query,8.該方法算出該字符串中每一個字符的個數,9.打印格式如:
    A——3
    B——3
    C——3
    D——2
    E——1
    主站蜘蛛池模板: 亚洲人成777在线播放| 亚洲精品视频久久久| 69堂人成无码免费视频果冻传媒| 黄色免费在线网站| 国产婷婷成人久久Av免费高清 | 亚洲精品天堂无码中文字幕| 亚洲精品国产国语| 亚洲熟妇久久精品| 亚洲s码欧洲m码吹潮| 久久精品国产亚洲AV未满十八| 亚洲国产精品嫩草影院| 亚洲av日韩精品久久久久久a| 亚洲国产精品无码观看久久| 精品国产亚洲AV麻豆 | 亚洲日韩国产精品无码av| 亚洲毛片一级带毛片基地| 亚洲人成电影在线观看青青| jiz zz在亚洲| 国产亚洲精品仙踪林在线播放| 思思久久99热免费精品6| 中文无码日韩欧免费视频| 国产免费无码AV片在线观看不卡| 一区二区在线免费观看| 免费国产作爱视频网站| 色视频色露露永久免费观看| 亚洲av再在线观看| 亚洲国产精品久久久久婷婷老年| 亚洲伊人久久大香线蕉啊| 日韩国产欧美亚洲v片| 精品多毛少妇人妻AV免费久久 | 精品亚洲国产成人av| sihu国产精品永久免费| 无码国产精品一区二区免费模式 | 久久免费观看国产精品88av| 在线看片韩国免费人成视频| 国产日产成人免费视频在线观看| 国产成人A亚洲精V品无码| 亚洲美女视频免费| 精品亚洲成a人在线观看| 精品亚洲永久免费精品| 免费国产黄线在线观看|