算法 字符串类问题(一)
无名之士 人气: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;
}
加载全部内容