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

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

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

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

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

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

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

Answer 1

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

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

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 2

Вы смотрели на Патрицию Три ? ( Реализация Java доступна в коде Google )

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

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

Answer 3

Согласитесь, ж / д, использование комплекта уместно. Ваш p-код переведен на python, слегка протестирован:

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

При каждой итерации строк вам необходимо проверять наличие значения по всем ранее встречающимся значениям. Это говорит мне о структуре типа hash или set.

Answer 4

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

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

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

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

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

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

Сначала нужно проверить предварительные условия.

РЕДАКТИРОВАТЬ: Использование набора сейчас. Изменен язык.