Tauschen LexOrder Union Finden

Question

So mache ich Interview Praxis Fragen und ich stieß auf diese: Gegeben eine Zeichenfolge str und Array von Paaren, die angibt, welche Indizes in der Zeichenfolge ausgetauscht werden können, geben Sie die lexikografisch größte Zeichenfolge, die daraus resultiert die erlaubten Swaps machen. Sie können Indizes beliebig oft tauschen.

Beispiel

Für str = "ABDC" und pairs = [[1, 4], [3, 4]], sollte die Ausgabe swapLexOrder (str, Paare) = "dbca" sein.

Durch Vertauschen der angegebenen Indizes erhalten Sie die Zeichenfolgen: "cbda", "cbad", "dbac", "dbca". Die lexikographisch größte Zeichenfolge in dieser Liste ist "dbca".

Ich habe eine funktionierende Antwort beteiligt finden Gewerkschaften bekam aber meine Antwort ist zu langsam:

[time limit] 4000ms (js) 
0 ≤ pairs.length ≤ 5000, 
pairs[i].length = 2. 
1 ≤ str.length ≤ 10^4 

Könnte mir jemand meinen Code optimieren helfen, seine Geschwindigkeit zu erhöhen? Heres den Code ich habe:

function swapLexOrder(str, pairs) { 
    if (!pairs.length){ 
     return str 
    } 

    answerHash = {} 
    unmoved = findUnmoved(pairs, str.length) 
    unionsArr = findUnions(pairs) 


    for (i in unmoved){ 
     answerHash[unmoved[i]] = str[(unmoved[i]-1)] 
    } 

    unionsArr.forEach(function(union){ 
     letters = [] 
     for (i in union){ 
      letters.push(str[(union[i]-1)]) 
     } 

     letters.sort() 
     union.sort(function(a,b){ 
      return b-a 
     }) 

     for (j in union){ 
      answerHash[union[j]] = letters[j] 
     } 
    }) 

    string = [] 
    for (keys in answerHash){ 
     string.push(answerHash[keys]) 
    } 
    return string.join('') 
} 



//if two pairs share a number they belong in the same array 
findUnions = function(pairs, unions){ 
    if (!unions){ 
     unions = [pairs[0]]; 
     pairs.shift(); 
    }else{ 
     if(pairs.length){ 
      unions.push(pairs[0]) 
      pairs.shift() 
     } 
    } 

    if (!pairs.length){ 
     return unions 
    } 

    unite = true 
    while (unite && pairs.length){ 
     unite = false 
     loop1: 
     for (i in unions){ 
      loop2: 
      for (j in pairs){ 
       if (unions[i].includes(pairs[j][0])){ 
        unions[i].push(pairs[j][1]) 
        pairs.splice(j, 1) 
        unite = true 
        break loop1 
       }else if (unions[i].includes(pairs[j][1])){ 
        unions[i].push(pairs[j][0]) 
        pairs.splice(j, 1) 
        unite = true 
        break loop1 
       } 
      } 
     } 
    } 
    return findUnions(pairs, unions) 
} 


findUnmoved = function(pairs, length){ 
    range = [] 
    for (var i=1;i<length+1;i++){ 
     range.push(i); 
    } 
    allNum = [].concat.apply([], pairs) 
    range = range.filter(function(x){ 
     return (!allNum.includes(x)) 
    }) 
    return range 
} 

Sein vermutlich die Funktion, die ich, die Gewerkschaften finden bin mit aber ich dachte, vielleicht habe ich es, ohne eine Hash tun könnte? Auch wenn Sie eine bessere Methode zur Lösung des Problems kennen, bin ich immer bereit, etwas Neues zu lernen. Vielen Dank!

Answer 1

Dieser arbeitet schneller.

function swapLexOrder(str, pairs) { 
//Turn pairs into edge lists: O(n+m) 
var graph = new Array(str.length).fill(0).map(e=>[]); 
for(var pair of pairs) { 
    graph[pair[0]-1].push(pair[1]-1); 
    graph[pair[1]-1].push(pair[0]-1); 
} 

//Build all the ccs with dfs: O(n+m) 
var ccs = [], ccnum = 0; 
for(var c in str) { 
    if(ccs[c]) 
     continue; 
    ccs[c] = ++ccnum; 
    var dfs = [...graph[c]]; 
    while(dfs.length) { 
     var d = dfs.shift(); 
     if(ccs[d]) 
      continue; 
     ccs[d] = ccnum; 
     dfs.push(...graph[d]); 
    } 
} 

//Group words by ccs: O(n) 
var ccWords = new Array(ccnum).fill(0).map(e=>[]); 
for(var c in str) { 
    ccWords[ccs[c]-1].push(str[c]); 
} 

//Sort all words: O(n log n) 
ccWords.map(e=>e.sort()); 

//Build the new string: O(n) 
var output = ""; 
for(var c in str) {output += ccWords[ccs[c]-1].pop(); } 
    return output; 
}