對于一個字符串,請設計一個高效算法，找到字符串的最長無重復字符的子串長度。 給定一個字符串A及它的長度n，請返回它的最長無重復字符子串長度。保證A中字符全部為小寫英文字符，且長度小于等于500。 測試樣例： “aabcb”,5 返回：3
有點類似動態規劃，但是比動態規劃簡單很多，首先利用一個vec記錄每個元素位置對應的最長無重復子串，利用map記錄每個字符出現的位置，對于一個新的元素位置，如果之前的map中沒有記錄那么最長子串就是前一個最長字符子串的長度加1，如果有記錄，看記錄的位置，如果記錄的位置在前一個字符最長子串的范圍內，則最長子串就是記錄位置和當前元素位置之間的元素，如果記錄的位置在前一個字符最長子串范圍外，那么最長子串就是前一個字符最長子串的長度加1。最后更新字符的記錄位置。循環進行處理即可。 代碼如下。
class DistinctSubstring {public: int longestSubstring(string A, int n) { if(n<=0) return 0; vector<int> vec(n,0); vec[0]=1; map<char,int> mymap; mymap[A[0]]=0; for(int i=1;i!=n;++i) { if(mymap.find(A[i])==mymap.end()) { mymap[A[i]]=i; vec[i]=vec[i-1]+1; } else { int temp=mymap[A[i]]; if(temp>=i-vec[i-1]) vec[i]=i-temp; else vec[i]=vec[i-1]+1; mymap[A[i]]=i; } } int max=INT_MIN; for(auto c:vec) { if(c>max) max=c; } return max; }};新聞熱點
疑難解答
