最長的子串沒有重複的人物角落案件

我在最近的一次採訪中被問到這個問題。我需要找到最長的substring而不重複字符。最長的子串沒有重複的人物角落案件

鑑於「abcabcbb」，答案是「abc」，其長度爲3

賦予「bbbbb」，答案是「b」，用的1

鑑於長度「 pwwkew」，答案是‘wke’，用3

長度。這是我想出了，我覺得它工作正常，但面試官沒有留下深刻印象，說我的解決方案可能不適合所有情況。

var str = "pwwkew"; 
 
    var longSubstring = function(str) { 
 
     var obj = {}; //map object 
 
     var count = 0; 
 
     var c = []; //count array to keep the count so far 
 
     for (var i = 0; i < str.length; ++i) { 
 
     //check if the letter is already in the map 
 
     if (str[i] in obj && obj[str[i]] !== i) { 
 
      c.push(count); //we encountered repeat character, so save the count 
 
      obj = {}; 
 
      obj[str[i]] = i; 
 
      count = 1; 
 
      continue; 
 
     } else { 
 
      obj[str[i]] = i; 
 
      ++count; 
 
     } 
 
     } 
 
     return Math.max.apply(null, c); 
 
    } 
 
    console.log(longSubstring(str)); //prints 3

誰能告訴我什麼是我的解決方案的問題？我認爲這是最好的:)並且也在O(n)時間內解決。

來源

2016-06-09 Wild Widow

什麼是「aaaabbbbaaaabbbbaaaabbbb」意味着返回？ – wot

@ e4en它應該返回2.任何ab，ba ...我的代碼也適用於這個 –

@WildWidow。如果輸入是'abc'，將輸出什麼.It返回-Infinity –

我想你的代碼的問題是，當整個句子中沒有重複的字母時，它會變得不合時宜。正如其中的一個評論「abc」所述，不會產生正確的結果。我的方法與您的方法略有不同，如下所示：

var str = "pwwkew", 
 
    data = Array.prototype.reduce.call(str, (p,c) => (p.test.includes(c) ? p.test = [c] 
 
                     : p.test.length >= p.last.length ? p.test = p.last = p.test.concat(c) 
 
                             : p.test.push(c) 
 
                     , p), {last:[], test:[]}), 
 
result = data.last.length; 
 
console.log(data); 
 
console.log(result);

在這種減少代碼我們最初開始與對象像{last:[], test:[]}和過去的人物一個接一個。如果收到的字符在我們的對象的test陣列中，我們立即重置test陣列以僅包含我們測試的字母（p.test = [c]行）。但是，如果接收到的字符不在我們的test數組中，那麼我們執行以下兩項中的任何一項。如果我們的test陣列的長度等於或長於last陣列的長度，那麼我們將當前字符添加到test陣列，並使last陣列= test陣列。（p.test.length >= p.last.length ? p.test = p.last = p.test.concat(c)一行）。但是，如果我們的test數組的長度比last數組的長度短，我們只需將當前字符添加到test數組，並同樣一直延續到字符串末尾的單個字符。

來源

2016-06-09 11:03:47 Redu

最長的子串沒有重複的人物角落案件

回答

相關問題