題目：
給定長度為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; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/264404.html
標籤：其他
上一篇：《贏》讀書筆記
下一篇：「SOL」謝特(LOJ)