2

我有一组字符串,我需要知道它们都不同的第一个索引。我可以想到两种方法来做到这一点:(下面的伪代码就在我的脑海中,可能有很多错误)

第一种方式:

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,在我所有的字符串上调用 substring(0,i) 将导致所有唯一值。”**

4

6 回答 6

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 集合,但任何集合都可以)。我什至会删除 lambda。再次未经测试,所以尽量不要将锋利的工具对准我的方向。

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;
    }
}
于 2009-05-20T16:57:48.923 回答
2

你看过Patricia trie吗?(谷歌代码上可用的Java实现

替代文字

构建trie,然后遍历数据结构,找到所有内部节点的最大字符串位置(上面函数中的黑点)。

这似乎应该是一个 O(n) 操作。我不确定您的 set 实现是否为 O(n) - 它“闻起来”像 O(n 2 ) 但我不确定。

于 2009-05-20T21:31:01.023 回答
1

按照您的建议使用套装,这正是正确的做法。

于 2009-05-20T16:40:03.530 回答
1

您应该能够在不排序的情况下执行此操作,并且在最坏的情况下只查看每个字符串中的每个字符一次。

这是一个将索引放到控制台的 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());
于 2009-05-20T17:14:18.513 回答
0
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++;
}

必须先检查前置条件。

编辑:现在使用一套。改变了语言。

于 2009-05-20T16:40:31.763 回答
0

这是我在 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

我没有写任何东西来处理当你到达最短单词末尾时没有找到最小索引的情况,但我相信你明白了。

于 2009-05-20T21:12:11.903 回答