Алгоритм для поиска первого индекса, где строки различны?

Question

У меня есть набор строк, и мне нужно знать первый индекс, где все они отличаются. Я могу думать о двух способов сделать это: (следующий псевдокод находится недалеко от верхней части моей головы, и может быть в значительной степени ошибка нагруженные)

Первый способ:

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 
} 

Это меня поражает, как валовой из-за использования установленной структуры данных, где, похоже, не требуется.

Второй способ:

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

Но это раздражает меня, что я должен запустить первый сорт, так как алгоритм сортировки, по самой своей природе, имеет доступ к информации, которую я ищу.

Несомненно, должен быть более эффективный способ, чем то, что я перечислил выше. В конце концов, я хотел бы абстрагировать его на любой тип массива, но это будет тривиально, и его проще рассматривать как проблему с строкой.

Любая помощь?

** ОБНОВЛЕНИЕ: Я, по-видимому, не очень хорошо себя объяснил. Если мои строки [«яблоко», «банан», «огурец», «банковское дело»), я хочу, чтобы функция вернула 3, потому что были две строки («банан» и «банковский»), которые соответствовали индексу 0, 1 и 2, поэтому 3 - это первый индекс, где они все уникально.

Как Даниил упомянуто ниже, лучший способ заявить свои потребности в том, что: «Я хочу, чтобы найти индекс, где я вызов подстроки (0, я) на все мои строках приведу все уникальные значения.» **

Answer 1

Используйте набор, как вы предлагали, это именно то, что нужно сделать.

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

Обязательно проверьте предварительные условия.

EDIT: Использование набора в настоящее время. Изменен langauge.

Answer 3

Это не проверено, но вот моя попытка. (Я могу сделать это более сложным, чем я должен, но я думаю, что это другой способ взглянуть на него.)

Основная идея состоит в том, чтобы скомпилировать группы элементов, которые соответствуют первому элементу, а затем найти максимальное уникальный индекс для каждой группы, проверяющий элементы в каждом последующем индексе.

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

---

А для версии без LINQ из выше (я изменю его использовать коллекцию List, но любая коллекция будет делать). Я даже удалю лямбду. Опять непроверенные, поэтому старайтесь не нацеливать острые орудия в моем направлении.

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

Вы должны быть в состоянии сделать это без сортировки и просмотра только каждого символа в каждой строке один раз в худшем случае.

здесь рубиновый скрипт, который помещает указатель на консоль:

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 

результат является 3.

Вот тот же общий фрагмент кода в C#, если это более разборчивыми для вас:

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

Принимаю ж/GS, использование множества является целесообразным. Ваш р-код транслируется в питон, слегка испытываться:

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() 

С каждой итерацией строк, необходимо проверить наличие значения в отношении всех ранее встречающихся значений. Это говорит о структуре хэш-функции или типа set-type.

Answer 6

Вот мое решение в 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 

я не писал ничего, чтобы обрабатывать случай, когда не минимальный индекс не найден к тому времени, когда вы достигнете конца самого короткого слова, но я конечно, вы получите эту идею.

Answer 7

Вы посмотрели Patricia trie? (Java implementation available on google code)

Сборка синтаксического дерева, затем траверс структуры данных, чтобы найти максимальное положение строки всех внутренних узлов (черные точки в функции выше).

Кажется, что это должна быть операция O (n). Я не уверен, является ли ваша реализация набора O (n) или нет - она ​​«пахнет» как O (n), но я не уверен.