假设我有：

• 托比
• 微小的
• 托里
• ly

是否有一种算法可以轻松在所有这些字符串的相同位置创建一个公共字符列表？ (在这种情况下，公共字符在位置0处为'T'，在位置3处为'y')

我尝试查看了一些用于DNA序列匹配的算法，但似乎大多数算法都只是用于查找通用子串，而不管它们的位置如何。

解决方案

回答

在特定位置查找所有字符串中常见的字符列表非常简单。只需在每个字符位置的每个字符串上迭代一次，一次只需要1个字符位置即可。如果任何字符串的字符都不是最接近的相邻字符串的字符的匹配项，则该位置不包含公共字符。

对于任何i = 0到长度-1 ......一旦找到Si [x]！= Si + 1 [x]，我们就可以跳到下一个位置x + 1.

其中Si是列表中的第i个字符串。 [x]是位置x处的字符。

回答

一些性能很差的通用代码O(n ^ 2)

str[] = { "Toby", "Tiny", "Tory", "Tily" };
result = null;
largestString = str.getLargestString(); // Made up function
str.remove(largestString)
for (i = 0; i < largestString.length; i++) {
   hits = 0;
   foreach (str as value) {
      if (i < value.length) {
         if (value.charAt(i) == largestString.charAt(i))
            hits++;
      }
   }
   if (hits == str.length)
      result += largestString.charAt(i);
}
print(str.items);

回答

我想不出什么特别优化的东西。

我们可以做这样的事情，这应该不会太难：

//c# -- assuming your strings are in a List<string> named Names
        int shortestLength = Names[0].Length, j;
        char[] CommonCharacters;
        char single;

        for (int i = 1; i < Names.Count; i++)
        {
            if (Names[i].Length < shortestLength) shortestLength = Names[i].Length;
        }

        CommonCharacters = new char[shortestLength];
        for (int i = 0; i < shortestLength; i++)
        {
            j = 1;
            single = Names[0][i];
            CommonCharacters[i] = single;
            while (j < shortestLength)
            {
                if (single != Names[j][i])
                {
                    CommonCharacters[i] = " "[0];
                    break;
                }
                j++;
            }
        }

这将为我们提供一系列与列表中所有内容相同的字符。

回答

这样的事呢？

strings = %w(Tony Tiny Tory Tily)
positions = Hash.new { |h,k| h[k] = Hash.new { |h,k| h[k] = 0 } }
strings.each { |str| 
  0.upto(str.length-1) { |i| 
    positions[i][str[i,1]]+=1 
  }
}

在执行结束时，结果将是：

positions = {
  0=>{"T"=>4},
  1=>{"o"=>2, "i"=>2}, 
  2=>{"l"=>1, "n"=>2, "r"=>1},
  3=>{"y"=>4}
}

回答

这是5行红宝石的算法：

#!/usr/bin/env ruby
chars = STDIN.gets.chomp.split("")
STDIN.each do |string|
  chars = string.chomp.split("").zip(chars).map {|x,y| x == y ? x : nil }
end
chars.each_index {|i| puts "#{chars[i]}  #{i}" if chars[i] }

将其放在commonletters.rb中。用法示例：

$ commonletters.rb < input.txt
T  0
y  3

假设input.txt包含：

Toby
Tiny
Tory
Tily

这应该与我们投入的任何输入配合使用。如果输入文件为空，它将中断，但是我们可以自己进行修复。这是O(n)(n是输入中的字符总数)。

回答

这是Python的一个普通版本：

items = ['Toby', 'Tiny', 'Tory', 'Tily']
tuples = sorted(x for item in items for x in enumerate(item))
print [x[0] for x in itertools.groupby(tuples) if len(list(x[1])) == len(items)]

哪些打印：

[(0, 'T'), (3, 'y')]

编辑：这是一个更好的版本，不需要创建(可能)巨大的元组列表：

items = ['Toby', 'Tiny', 'Tory', 'Tily']
minlen = min(len(x) for x in items)
print [(i, items[0][i]) for i in range(minlen) if all(x[i] == items[0][i] for x in items)]

回答

虚张声势：

CL-USER> (defun common-chars (&rest strings)
           (apply #'map 'list #'char= strings))
COMMON-CHARS

只需传递字符串即可：

CL-USER> (common-chars "Toby" "Tiny" "Tory" "Tily")
(T NIL NIL T)

如果我们想要角色本身：

CL-USER> (defun common-chars2 (&rest strings)
           (apply #'map
                  'list
                  #'(lambda (&rest chars)
                      (when (apply #'char= chars)
                        (first chars))) ; return the char instead of T
                  strings))
COMMON-CHARS2

CL-USER> (common-chars2 "Toby" "Tiny" "Tory" "Tily")
(#\T NIL NIL #\y)

如果我们不在乎posiiton，而只想要一个常见字符列表：

CL-USER> (format t "~{~@[~A ~]~}" (common-chars2 "Toby" "Tiny" "Tory" "Tily"))
T y 
NIL

我承认这不是一种算法...只是使用现有功能以Lisp方式实现的一种方法

如前所述，如果我们想手动执行此操作，则可以循环比较给定索引处的所有字符。如果它们都匹配，请保存匹配的字符。

回答

#include <iostream>

int main(void)
{
    char words[4][5] = 
    {
        "Toby",
        "Tiny",
        "Tory",
        "Tily"
    };

    int wordsCount = 4;
    int lettersPerWord = 4;

    int z;
    for (z = 1; z < wordsCount; z++)
    {
        int y;
        for (y = 0; y < lettersPerWord; y++)
        {
            if (words[0][y] != words[z][y])
            {
                words[0][y] = ' ';
            }
        }
    }

    std::cout << words[0] << std::endl;

    return 0;
}