基於兩個字符串的差異創建所有變體

Question

我確實有一個等待兩個字符串的函數。我想返回包含所有可能變化的單詞列表，這些變體可以根據差異創建。

getAllVersions('cso','cső'); //--> [cso, cső] 
getAllVersions('eges','igis'); //--> [eges, igis, egis, iges] 

到目前爲止，我已經創建了計算差異並保存其位置的函數。你有什麼想法如何繼續？

public ArrayList<String> getAllVersions(String q, String qW) { 
      int differences = 0; 
      ArrayList<Integer> locations = new ArrayList<>(); 
      ArrayList<String> toReturn = new ArrayList<>(); 

      for (int i = 0; i < q.length(); i++) { 
       if (q.charAt(i) != q.charAt(i)) { 
        differences++; 
        locations.add(i); 
       } 
      } 
        toReturn.add(q); 
        toReturn.add(qW); 
      for (int i = 0; i < q.length(); i++) { 
       for (int j = 0; j < q.length(); j++) { 

       } 
      } 
      return toReturn; 
     } 
    } 

Answer 1

這裏是一個遞歸解決方案
時間複雜度：O（N）

public List<String> allVariants(String x, String y) { 
    if ((x == null || x.isEmpty()) && (y == null || y.isEmpty())) { 
     return new ArrayList<String>(); 
    } 
    List<String> l = new ArrayList<String>(); 
    if (x == null || x.isEmpty()) { 
     l.add(y); 
     return l; 
    } 
    if (y == null || y.isEmpty()) { 
     l.add(x); 
     return l; 
    } 
    char xc = x.charAt(0); 
    char yc = y.charAt(0); 
    List<String> next = allVariants(x.substring(1), y.substring(1)); 
    if (next.isEmpty()) { 
     l.add(xc + ""); 
     if (xc != yc) { 
      l.add(yc + ""); 
     } 
    } else { 
     for (String e : next) { 
      l.add(xc + e); 
      if (xc != yc) { 
       l.add(yc + e); 
      } 
     } 
    } 
    return l; 
} 

測試代碼：

public static void main(String[] args) { 
    List<String> l = new Test().allVariants("igis", "eges"); 
    for (String x : l) { 
     System.out.println(x); 
    } 
} 

輸出：

igis 
egis 
iges 
eges 

Answer 2

for (int i = 0; i < q.length(); i++) //as before, but a little simplified... 
    if (q.charAt(i) != q.charAt(i)) 
     locations.add(i); 

//Now we're going to create those variations. 

toReturn.add(q); //Start with the first string 

for each location we found 
    Additions = a new empty list of Strings 
    for each element in toReturn 
     create a new String which is a copy of that element 
     alter its location-th character to match the corresponding char in qW 
     append it to Additions 
    append Additions to toReturn 

當做到這一點，toReturn應符合Q開始，以每週一次結束，有之間的所有變化。