Algorithmus, um den ersten Index zu finden, wo Strings unterschiedlich sind?

Question

Ich habe eine Sammlung von Strings, und ich muss den ersten Index wissen, wo sie sich alle unterscheiden. Ich kann mir zwei Möglichkeiten, dies zu tun: (das folgende Pseudo-Code direkt an der Spitze von meinem Kopf und kann stark fehler beladen)

Erster Weg:

var minLength = [go through all strings finding min length]; 
var set = new set() 
for(i=0;i<minlength;i++) 
{ 
    for(str in strings) 
    { 
    var substring = str.substring(0,i); 
    if(set.contains(substring)) 
     break; // not all different yet, increment i 
    set.add(substring) 
    } 
    set.clear(); // prepare for next length of substring 
} 

Das erscheint mir als Brutto wegen der Verwendung einer festgelegten Datenstruktur, wo es so aussieht, als ob man nicht benötigt wird.

Zweiter Weg:

var minLength = [go through all strings finding min length]; 
strings.sort(); 
for(i=0;i<minlength;i++) 
{ 
    boolean done = true; 
    char last = null; 
    for(str in strings) 
    { 
    char c = str[i]; 
    if(c == last) 
    { 
     // not all different yet, increment i 
     done = false; 
     break; 
    } 
    last = c; 
    } 
    if(done) 
    return i; 
} 

Aber es ärgert mich, dass ich die Art zuerst laufen, weil der Sortieralgorithmus, seine Natur nach, den Zugang zu den Informationen hat, die ich suche.

Sicher muss es einen effizienteren Weg als das, was ich oben aufgeführt habe. Irgendwann würde ich es gerne für jede Art von Array abstrahieren, aber das wird trivial sein und es ist einfacher, es als String-Problem zu betrachten.

Irgendwelche Hilfe?

** UPDATE: Ich habe mich anscheinend nicht sehr gut erklären können. Wenn meine Strings ["apple", "banana", "gurke", "banking"] sind, möchte ich, dass die Funktion 3 zurückgibt, weil zwei Strings ("banana" und "banking") durch den Index 0 übereinstimmten. 1, und 2, so ist 3 der erste Index, wo sie alle einzigartig sind.

Als Daniel unten erwähnt, eine bessere Art und Weise meine Bedürfnisse zu erklären ist, dass: „Ich Index finden möchte ich wo Teilzeichenfolge Aufruf (0, i) auf alle meine Saiten in allen eindeutigen Werten führen.“ **

Answer 1

Verwenden Sie das Set wie Sie vorgeschlagen haben, das ist genau das Richtige.

Answer 2

int i = 0; 
while(true) 
{ 
    Set set = new Set(); 
    for(int j = 0; j < strings.length; j++) 
    { 
     if(i >= strings[j].length) return i; 
     String chr = strings[j].charAt(i); 
     if(set.hasElement(chr)) 
      break; 
     else 
      set.addElement(chr); 
    } 
    if(set.size() == strings.length) 
     return i; 
    i++; 
} 

Zuerst müssen die Voraussetzungen überprüft werden.

EDIT: Verwenden Sie jetzt ein Set. Geänderte Sprache.

Answer 3

Dies ist nicht getestet, aber hier ist mein Versuch. (Ich mache es vielleicht komplizierter, als ich muss, aber ich denke, es ist eine andere Art, es zu betrachten.)

Die Grundidee besteht darin, Gruppen von Elementen zu kompilieren, die am ersten Element übereinstimmen, dann die max eindeutiger Index für jede Gruppe, Prüfen von Elementen bei jedem aufeinanderfolgenden Index.

int FirstUniqueIndex<T>(IEnumerable<IEnumerable<T>> myArrayCollection) 
{ 
    //just an overload so you don't have to specify index 0 all the time 
    return FirstUniqueIndex(myArrayCollection, 0); 
} 

int FirstUniqueIndex<T>(IEnumerable<IEnumerable<T>> myArrayCollection, int StartIndex) 
{ 
    /* Group the current collection by the element at StartIndex, and 
    * return a collection of these groups. Additionally, we're only interested 
    * in the groups with more than one element, so only get those.*/ 

    var groupsWithMatches = from var item in myArrayCollection //for each item in the collection (called "item") 
          where item.Length > StartIndex //that are long enough 
          group by item[StartIndex] into g //group them by the element at StartIndex, and call the group "g" 
          where g.Skip(1).Any() //only want groups with more than one element 
          select g; //add the group to the collection 

    /* Now "groupsWithMatches" is an enumeration of groups of inner matches of 
    * your original arrays. Let's process them... */ 

    if(groupsWithMatches.Any()) 
     //some matches were found - check the next index for each group 
     //(get the maximum unique index of all the matched groups) 
     return groupsWithMatches.Max(group => FirstUniqueIndex(group, StartIndex + 1)); 
    else 
     //no matches found, all unique at this index 
     return StartIndex; 
} 

---

Und für die nicht-LINQ-Version des oben (ich werde es eine Liste Sammlung verwenden ändern, aber jede Sammlung übernommen werden können). Ich werde sogar das Lambda entfernen. Wieder ungeprüft, also versuche keine scharfen Geräte in meine Richtung zu richten.

int FirstUniqueIndex<T>(List<List<T>> myArrayCollection, int StartIndex) 
{ 
    /* Group the current collection by the element at StartIndex, and 
    * return a collection of these groups. Additionally, we're only interested 
    * in the groups with more than one element, so only get those.*/ 

    Dictionary<T, List<List<T>>> groupsWithMatches = new Dictionary<T, List<List<T>>>(); 

    //group all the items by the element at StartIndex 
    foreach(var item in myArrayCollection) 
    { 
     if(item.Count > StartIndex) 
     { 
      List<List<T>> group; 
      if(!groups.TryGetValue(item[StartIndex], out group)) 
      { 
       //new group, so make it first 
       group = new List<List<T>>(); 
       groups.Add(item[StartIndex], group); 
      } 

      group.Add(Item); 
     } 
    } 

    /* Now "groups" is an enumeration of groups of inner matches of 
    * your original arrays. Let's get the groups with more than one item. */ 

    List<List<List<T>>> groupsWithMatches = new List<List<List<T>>>(groups.Count); 

    foreach(List<List<T> group in groupsWithMatches) 
    { 
     if(group.Count > 1) 
      groupsWithMatches.Add(group); 
    } 

    if(groupsWithMatches.Count > 0) 
    { 
     //some matches were found - check the next index for each group 
     //(get the maximum unique index of all the matched groups) 

     int max = -1; 
     foreach(List<List<T>> group in groupsWithMatches) 
     { 
      int index = FirstUniqueIndex(group, StartIndex + 1); 
      max = index > max ? index : max; 
     } 
     return max; 
    } 
    else 
    { 
     //no matches found, all unique at this index 
     return StartIndex; 
    } 
} 

Answer 4

Sie sollten in der Lage sein, dies ohne Sortierung zu tun, und nur im schlimmsten Fall jedes Zeichen in jeder Zeichenfolge einmal zu betrachten.

hier ist ein Ruby-Skript, das den Index an die Konsole setzt:

mystrings = ["apple", "banana", "cucumber", "banking"] 
minlength = getMinLengthString(mystrings) #not defined here 

char_set = {} 

(0..minlength).each do |char_index| 
    char_set[mystrings[0][char_index].chr] = 1 
    (1..mystrings.length).each do |string_index| 
    comparing_char = mystrings[string_index][char_index].chr 
    break if char_set[comparing_char] 
    if string_index == (mystrings.length - 1) then 
     puts string_index 
     exit 
    else 
     char_set[comparing_char] = 1 
    end  
    end 
    char_set.clear 
end 
puts minlength 

das Ergebnis 3.

Hier sind die gleichen allgemeinen Schnipsel in C#, wenn sie besser lesbar für Dich ist:

string[] mystrings = { "apple", "banana", "cucumber", "banking" }; 

//defined elsewhere... 
int minlength = GetMinStringLengthFromStringArray(mystrings); 

Dictionary<char, int> charSet = new Dictionary<char, int>(); 

for (int char_index = 0; char_index < minlength; char_index++) 
{ 
    charSet.Add(mystrings[0][char_index], 1); 

    for (int string_index = 1; string_index < mystrings.Length; string_index++) 
    { 
     char comparing_char = mystrings[string_index][char_index]; 

     if (charSet.ContainsKey(comparing_char)) 
     { 
      break; 
     } 
     else 
     { 
      if (string_index == mystrings.Length - 1) 
      { 
        Console.Out.WriteLine("Index is: " + string_index.ToString()); 
        return; 
      } 
      else 
      { 
        charSet.Add(comparing_char, 1); 
      } 
     } 
    } 

    charSet.Clear(); 
} 
Console.Out.WriteLine("Index is: " + minlength.ToString()); 

Answer 5

w/gs Agree, die Verwendung von Set ist geeignet. Ihr p-Code zu Python übersetzt, leicht getestet:

minlen = min(len(x) for x in strings) 
myset = set() 
for i in range(minlen): 
    for s in strings: 
     sub = s[:i+1] 
     if sub in myset: 
      break 
     myset.add(sub) 
    if len(myset) == len(strings): 
     print i 
     break 
    myset.clear() 

Mit jeder Iteration durch Strings, müssen Sie auf die Existenz eines Wertes gegenüber allen bisher aufgetretenen Werte überprüfen. Das sagt mir Hash- oder Set-Type-Struktur.

Answer 6

Hier ist meine Lösung in Python:

words = ["apple", "banana", "cucumber", "banking"] 

for i in range(len(min(words))): 
    d = defaultdict(int) 
    for word in words: 
     d[word[i]] += 1 
    if max(d.values()) == 1: 
     return i 

ich nicht in etwas geschrieben habe, den Fall zu behandeln, in denen kein Mindestindex durch die Zeit, die Sie das Ende des kürzesten Wortes erreichen gefunden wird, aber ich bin Sicher hast du die Idee.

Answer 7

hast du dir eine Patricia trie angesehen? (Java implementation available on google code)

bauen die Trie, dann durchqueren die Datenstruktur die maximale String Position aller internen Knoten (schwarze Punkte in der Funktion oben) zu finden.

Dies scheint wie eine O (n) -Operation sein sollte. Ich bin mir nicht sicher, ob Ihre Set-Implementierung ist O (n) oder nicht - es "riecht" wie O (n) aber ich bin mir nicht sicher.