由最長公共起始子字符串組成的字符串組

Question

這是問題所在。說我有這些字符串：

• 蘋果iPad迷你32GB
• 蘋果iPad迷你64GB
• 蘋果iPad空氣64GB
• 蘋果iPad空氣32GB
• 松下GH4
• 三星S2銀河
• samsung s2 galaxy red
• samsung s3 galaxy

我想這些字符串進行分組如下：

• 蘋果iPad迷你：蘋果iPad迷你32GB，蘋果iPad迷你64GB]
• 蘋果iPad的空氣：蘋果iPad空氣64GB，蘋果ipad的32GB]
• 松下GH4：松下GH4]
• 三星S2星系：三星S2星系，三星S2星系紅色]
• 三星S3星系

關鍵是將項目的名稱與其屬性（顏色，內存容量等）分開。

我用這個算法尋找最長公共子： link

你們可以分享您的想法？無需代碼或實施。謝謝。

編輯：

this.data = _.sortBy(this.data, function(item) { 
     return item.title; 
    }); 

    var i = 0; 
    var groups = {}; 
    var len = this.data.length - 1; 
    while(i < len) { 
     var key = this.lcs(this.data[i][this.attr], this.data[i+1][this.attr]) || this.data[i][this.attr]; 
     groups[key] = true; 
     i++; 
     while(this.data[i][this.attr].startsWith(key) && i < len) { 
      i++; 
     } 
    } 
    console.log(groups) 

這個偉大的工程（測試只增加鍵）。但我也想添加三星s3星系列表。感謝幫助傢伙！

Answer 1

如果你只是想簡單地按最長公共前綴進行分組（即，即使「apple ipad」會產生更大的組，也會選擇「apple ipad mini」），那麼可能是這樣的？

sort the list 
i = 0 
while i < end of list: 
    key = longest common prefix of list[i] & list[i + 1] 
     or list[i] if the common prefix is less than (1?) words or i is the last index 
    groups[key] = list[i++] 
    while key is prefix of list[i]: 
    add list[i++] to groups[key] 

Answer 2

試圖用比較兩個字符串用同樣的話和查找，如果單詞的長度較小，則前面的路徑來解決這個問題。

function groupObject(i, l) { 
 
    return { item: i, length: l }; 
 
} 
 

 
function group(r, a, i, o) { 
 
    var rr = r.item.split(' '), 
 
     aa = a.split(' '), 
 
     j = 0, 
 
     key, keys = []; 
 

 
    while (aa[j] === rr[j]) { 
 
     keys.push(aa[j]); 
 
     j++; 
 
    } 
 
    if (keys.length < r.length && i < o.length - 1) { 
 
     return group(groupObject(o[i + 1], 0), a, Number.MAX_VALUE, o); 
 
    } 
 
    key = keys.join(' '); 
 
    if (!key || keys.length < r.length && i === o.length - 1) { 
 
     key = a; 
 
    } 
 
    grouped[key] = grouped[key] || []; 
 
    grouped[key].push(a); 
 
    return groupObject(a, keys.length); 
 
} 
 

 
var data = ['apple ipad mini 32gb', 'apple ipad mini 64gb', 'apple ipad air 64gb', 'apple ipad air 32gb', 'panasonic gh4', 'samsung s2 galaxy', 'samsung s2 galaxy red', 'samsung s3 galaxy'], 
 
    grouped = {}; 
 

 
data.reduce(group, groupObject(data[1], 0)); 
 
document.write('<pre>' + JSON.stringify(grouped, 0, 4) + '</pre>');