スワップLexOrder Union Find

Question

私はインタビューの練習問題をしています。 文字列strとその文字列内のどのインデックスをスワップできるかを示すペアの配列が与えられている場合、辞書順に最大の文字列を返します許可されたスワップを行う。インデックスを何度も交換することができます。

例

STR = "ABDC" とペア=ために[1,4]、[3,4]、出力は swapLexOrder（STR、ペア）= "DBCA" でなければなりません。

指定されたインデックスをスワップすると、 "cbda"、 "cbad"、 "dbac"、 "dbca"という文字列が取得されます。このリストの辞書編集的に最大の文字列は "dbca"です。

私が見つけ組合が関与する作業の答えを持っているが、私の答えは遅すぎる：

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

誰かが私にはその速度を高めるために自分のコードを微調整に役立つだろうか？私が持っている は、相続人のコード：

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 
} 

その私が組合を見つけるために使用していますが、私は多分私はハッシュを作成せずにそれを行うことを考えていた、おそらく機能？また、問題を解決するより良い方法を知っているなら、私は常に新しいものを学ぶために立ち上がっています。ありがとう！

Answer 1

これはより速く動作します。

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; 
}