亲宝软件园·资讯

展开

算法 字符串类问题(一)

无名之士 人气:0

题目:

给定长度为m的字符串aim,以及一个长度为n的字符串str。

问:

能否在str中找到一个长度为m的连续子串,使得这个子串刚好由aim的m个字符组成,顺序无所谓。

返回:

返回任意满足条件的一个子串的起始位置,未找到返回-1。

例:

str = "abcd"  aim = "dc"

返回值: 2

 

方法1:最简单暴力的方法,取所有子串,并对每个子串、aim字符串排序判断是否相等即可。代码略去。时间复杂度O(n^3 *log2^n)。

方法2:对方法以优化,只取和aim长度相同的子串进行比较。但此处比较是否相等,使用O(m)复杂度的算法。时间复杂度O(m*n)。思路如下: 

既然要比较的两个字符串长度相同,那么用一个数组记录aim中每个字符出现的次数(称之为欠账数),之后将子串中的每个字符与之对应的欠账数进行减操作,如果减之前出现0,那么直接返回不匹配,最后返回匹配。

比如:子串 = “cdd"     aim = "ccd"   则欠账数为[......a=0,......c=2,d=1,......]。遍历子串以此为,c则欠账数[......a=0,....c=1,d=1,....],d则[......a=0,....c=1,d=0,....],d此时欠账数d=0,所以不匹配。 

    public static int getIndex2(String str, String aim){
        if(str == null || aim == null || str.length() < aim.length()) return -1;
        for(int i = 0; i <= str.length() - aim.length(); i++)
        {
            if(isCountEqual(str, i, aim)) return i;
        }
        return -1;
    }
    public static boolean isCountEqual(String str, int lift, String aim){
        int[] count = new int[256];
        for(int i = 0; i < aim.length(); i++){
            count[aim.charAt(i)] ++;
        }
        for(int i = 0; i < aim.length(); i++){
            if(count[str.charAt(lift + i)]-- == 0) return false;
        }
        return true;
    }

方法3:方法2已经对欠账数组有了了解,那么方法3就是利用欠账数组,和一个多还数量标记,实现时间复杂度O(n)。思路如下:

在str字符串中找到前m个字符进行还账,即前m个字符和欠账数进行比较,如果当前字符欠账数大于0,则减1,否则减1同时,多还数量(初始为0)加1。之后对str字符从下标m进行逐个还账,一开始

进行判断,多还数量是否为0,如果是,则返回当前下标值减去m,否则当前下标位置字符还账(还账之前判断此字符欠账数,如果小于等于0,则多还数量加1),并且当前下标值减去m的位置字符进行欠账(欠账之前判断此字符欠账数,如果小于0,则多还数量减1)循环退出之后,也要判断一次多还数量是否为0,此为判断最后一次还账和欠账之后的结果是否满足。

    public static int getIndex(String str, String aim){
        if(str == null || aim == null || str.length() < aim.length()) return -1;
        int[] count = new int[256];
        int index = 0, M = aim.length(),inVslid = 0, StrM= str.length();
        for(int i = 0; i < M; i++){
            count[aim.charAt(i)] ++;
        }
        for(;index < M; index++){
            if(count[str.charAt(index)]-- <= 0) inVslid ++;
        }
        for(;index < StrM; index++){
            if(inVslid == 0) return index - M;
            if(count[str.charAt(index)]-- <= 0) inVslid++;
            if(count[str.charAt(index - M)]++ < 0) inVslid--;
        }
        return inVslid == 0?index - M:-1;
    }

 

加载全部内容

相关教程
猜你喜欢
用户评论