javascript - 文字列のセットから最も長い共通の開始部分文字列を検索します

Question

これは、比較的些細な問題に対して最も洗練されたJavaScript、Ruby、またはその他のソリューションを考え出すための課題です。

この問題は、最長の一般的な部分文字列問題のより具体的なケースです。配列内で最も長い共通の開始部分文字列を見つけるだけで済みます。これにより、問題が大幅に簡素化されます。

たとえば、の最長の部分文字列[interspecies, interstelar, interstate]は「inters」です。ただし、で「ific」を見つける必要はありません[specifics, terrific]。

シェルのようなタブ補完に関する回答の一部として、JavaScriptでソリューションをすばやくコーディングすることで、問題を解決しました（テストページはこちら）。これがその解決策ですが、少し調整されています。

function common_substring(data) {
  var i, ch, memo, idx = 0
  do {
    memo = null
    for (i=0; i < data.length; i++) {
      ch = data[i].charAt(idx)
      if (!ch) break
      if (!memo) memo = ch
      else if (ch != memo) break
    }
  } while (i == data.length && idx < data.length && ++idx)

  return (data[0] || '').slice(0, idx)
}

このコードは、Rubyの同様のソリューションとともにこのGistで利用できます。要旨をgitリポジトリとして複製して試してみることができます。

$ git clone git://gist.github.com/257891.git substring-challenge

私はそれらの解決策にあまり満足していません。よりエレガントで実行の複雑さを軽減することで解決できるかもしれないと感じています。そのため、このチャレンジを投稿しています。

私は答えとして、私が最もエレガントまたは簡潔だと思う解決策を受け入れるつもりです。たとえば、私が思いついたクレイジーなRubyハックは&、Stringで演算子を定義することです。

# works with Ruby 1.8.7 and above
class String
  def &(other)
    difference = other.to_str.each_char.with_index.find { |ch, idx|
      self[idx].nil? or ch != self[idx].chr
    }
    difference ? self[0, difference.last] : self
  end
end

class Array
  def common_substring
    self.inject(nil) { |memo, str| memo.nil? ? str : memo & str }.to_s
  end
end

JavaScriptまたはRubyのソリューションが推奨されますが、何が起こっているのかを説明する限り、他の言語で巧妙なソリューションを披露することができます。標準ライブラリのコードのみを使用してください。

更新：私のお気に入りのソリューション

kennebecによるJavaScriptの並べ替えソリューションを「答え」として選択したのは、それが予想外で天才的であると感じたからです。実際の並べ替えの複雑さを無視すると（言語の実装によって無限に最適化されると想像してみてください）、ソリューションの複雑さは2つの文字列を比較するだけです。

その他の優れたソリューション：

FMによる「regexgreed」は、把握するのに1、2分かかりますが、その優雅さがあなたを襲います。イェフダカッツも正規表現ソリューションを作成しましたが、より複雑です
commonprefixPythonの場合— Roberto Bonvalletは、この問題を解決するためにファイルシステムパスを処理するために作成された機能を使用しました
Haskellのワンライナーは圧縮されているかのように短く、美しい
簡単なRubyワンライナー

参加していただきありがとうございます！コメントからわかるように、私は多くのことを学びました（Rubyについてさえ）。

score 55 · Accepted Answer

好みの問題ですが、これは単純なjavascriptバージョンです。配列を並べ替えてから、最初と最後の項目だけを調べます。

//配列内の最も長い共通の開始部分文字列

function sharedStart(array){
    var A= array.concat().sort(), 
    a1= A[0], a2= A[A.length-1], L= a1.length, i= 0;
    while(i<L && a1.charAt(i)=== a2.charAt(i)) i++;
    return a1.substring(0, i);
}

デモス

sharedStart(['interspecies', 'interstelar', 'interstate'])  //=> 'inters'
sharedStart(['throne', 'throne'])                           //=> 'throne'
sharedStart(['throne', 'dungeon'])                          //=> ''
sharedStart(['cheese'])                                     //=> 'cheese'
sharedStart([])                                             //=> ''
sharedStart(['prefix', 'suffix'])                           //=> ''

score 38 · Accepted Answer

Pythonの場合：

>>> from os.path import commonprefix
>>> commonprefix('interspecies interstelar interstate'.split())
'inters'

score 9 · Accepted Answer

9

Rubyワンライナー：

l=strings.inject{|l,s| l=l.chop while l!=s[0...l.length];l}

于 2009-12-16T18:00:44.440 に答える

score 9 · Accepted Answer

すべての文字列が異なるまでトラバースしてから、このポイントまでサブ文字列を取得する必要があります。

擬似コード：

loop for i upfrom 0
     while all strings[i] are equal
     finally return substring[0..i]

Common Lisp：

(defun longest-common-starting-substring (&rest strings)
  (loop for i from 0 below (apply #'min (mapcar #'length strings))
     while (apply #'char=
                  (mapcar (lambda (string) (aref string i))
                          strings))
     finally (return (subseq (first strings) 0 i))))

score 9 · Accepted Answer

私のHaskellワンライナー：

import Data.List

commonPre :: [String] -> String
commonPre = map head . takeWhile (\(x:xs)-> all (==x) xs) . transpose

編集：barkmadleyは以下のコードの良い説明をしました。transposeまた、haskellは遅延評価を使用しているので、 ;の使用について怠惰になる可能性があることも付け加えておきます。共通プレフィックスの終わりを見つけるために必要な範囲でのみリストを転置します。

score 6 · Accepted Answer

それを行うさらに別の方法：正規表現の貪欲を使用します。

words = %w(interspecies interstelar interstate)
j = '='
str = ['', *words].join(j)
re = "[^#{j}]*"

str =~ /\A
    (?: #{j} ( #{re} ) #{re} )
    (?: #{j}    \1     #{re} )*
\z/x

p $1

そして、ワンライナー、mislav（50文字）の礼儀：

p ARGV.join(' ').match(/^(\w*)\w*(?: \1\w*)*$/)[1]

score 4 · Accepted Answer

Pythonでは、別の回答で示した既存の関数以外は何も使用しませんでしたが、commonprefix車輪の再発明を行うのは仕方がありませんでした:P。これは私のイテレータベースのアプローチです。

>>> a = 'interspecies interstelar interstate'.split()
>>>
>>> from itertools import takewhile, chain, izip as zip, imap as map
>>> ''.join(chain(*takewhile(lambda s: len(s) == 1, map(set, zip(*a)))))
'inters'

編集：これがどのように機能するかの説明。

zip一度にの各アイテムの1つを取る要素のタプルを生成しますa。

In [6]: list(zip(*a))  # here I use list() to expand the iterator
Out[6]:
[('i', 'i', 'i'),
 ('n', 'n', 'n'),
 ('t', 't', 't'),
 ('e', 'e', 'e'),
 ('r', 'r', 'r'),
 ('s', 's', 's'),
 ('p', 't', 't'),
 ('e', 'e', 'a'),
 ('c', 'l', 't'),
 ('i', 'a', 'e')]

これらのアイテムをマッピングsetすることで、一連のユニークな文字が得られます。

In [7]: list(map(set, _))  # _ means the result of the last statement above
Out[7]:
[set(['i']),
 set(['n']),
 set(['t']),
 set(['e']),
 set(['r']),
 set(['s']),
 set(['p', 't']),
 set(['a', 'e']),
 set(['c', 'l', 't']),
 set(['a', 'e', 'i'])]

takewhile(predicate, items)述語がTrueのときに、これから要素を取得します。この特定のケースでは、setsに1つの要素がある場合、つまり、すべての単語がその位置に同じ文字を持っている場合：

In [8]: list(takewhile(lambda s: len(s) == 1, _))
Out[8]:
[set(['i']),
 set(['n']), 
 set(['t']), 
 set(['e']), 
 set(['r']), 
 set(['s'])]

この時点で、反復可能なセットがあり、それぞれに、探していたプレフィックスの1文字が含まれています。文字列を作成するために、chainそれらを1つの反復可能オブジェクトに変換し、そこから文字を取得joinして最終的な文字列にします。

イテレータを使用する魔法は、すべてのアイテムがオンデマンドで生成されることです。したがって、takewhileアイテムの要求を停止すると、その時点で圧縮が停止し、不要な作業は行われません。私のワンライナーの各関数呼び出しには、暗黙的forおよび暗黙的がありbreakます。

score 3 · Accepted Answer

これはおそらく最も簡潔な解決策ではありませんが（このためのライブラリがすでにあるかどうかによって異なります）、1つの洗練された方法はトライを使用することです。スキームインタープリターでタブ補完を実装するためにtrysを使用します。

http://github.com/jcoglan/heist/blob/master/lib/trie.rb

例えば：

tree = Trie.new
%w[interspecies interstelar interstate].each { |s| tree[s] = true }
tree.longest_prefix('')
#=> "inters"

また、チャネル名をバイユープロトコルのワイルドカードと照合するためにも使用します。これらを参照してください：

http://github.com/jcoglan/faye/blob/master/client/channel.js

http://github.com/jcoglan/faye/blob/master/lib/faye/channel.rb

score 3 · Accepted Answer

それを楽しむために、（SWI-）PROLOGで書かれたバージョンを次に示します。

common_pre([[C|Cs]|Ss], [C|Res]) :-
  maplist(head_tail(C), [[C|Cs]|Ss], RemSs), !,
  common_pre(RemSs, Res).
common_pre(_, []).

head_tail(H, [H|T], T).

ランニング：

?- S=["interspecies", "interstelar", "interstate"], common_pre(S, CP), string_to_list(CPString, CP).

与える：

CP = [105, 110, 116, 101, 114, 115],
CPString = "inters".

説明：

（SWI-）PROLOGは、文字列を文字コード（数字）のリストとして扱います。すべての述語common_pre/2は再帰的にパターンマッチングを行い、すべてのリスト（すべての文字列、）のリストCの最初のリスト（文字列、）の先頭から最初のコード（）を選択し、一致するコードを結果に追加します。すべてのリスト（文字列）のすべての（残りの）ヘッドに共通です。それ以外の場合は終了します。[C|Cs][[C|Cs]|Ss]C

素敵で、清潔で、シンプルで効率的です... :)

score 3 · Accepted Answer

@Svanteのアルゴリズムに基づくjavascriptバージョン：

function commonSubstring(words){
    var iChar, iWord,
        refWord = words[0],
        lRefWord = refWord.length,
        lWords = words.length;
    for (iChar = 0; iChar < lRefWord; iChar += 1) {
        for (iWord = 1; iWord < lWords; iWord += 1) {
            if (refWord[iChar] !== words[iWord][iChar]) {
                return refWord.substring(0, iChar);
            }
        }
    }
    return refWord;
}

score 3 · Accepted Answer

kennebec、Florian F、jberrymanによる回答を組み合わせると、次のHaskellワンライナーが得られます。

commonPrefix l = map fst . takeWhile (uncurry (==)) $ zip (minimum l) (maximum l)

1Control.Arrowつでポイントフリーフォームを取得できます：

commonPrefix = map fst . takeWhile (uncurry (==)) . uncurry zip . (minimum &&& maximum)

score 2 · Accepted Answer

Python 2.6 (r26:66714, Oct  4 2008, 02:48:43) 

>>> a = ['interspecies', 'interstelar', 'interstate']

>>> print a[0][:max(
        [i for i in range(min(map(len, a))) 
            if len(set(map(lambda e: e[i], a))) == 1]
        ) + 1]

inters

i for i in range(min(map(len, a)))、最大ルックアップの数は、最短の文字列の長さを超えることはできません。この例では、これは次のように評価されます[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
len(set(map(lambda e: e[i], a)))、1）i-thリスト内の各文字列の文字の配列を作成します。2）それからセットを作ります。3）セットのサイズを決定します
[i for i in range(min(map(len, a))) if len(set(map(lambda e: e[i], a))) == 1]、セットのサイズが1である文字のみを含めます（その位置のすべての文字は同じでした..）; ここでそれは評価します[0, 1, 2, 3, 4, 5]
最後に、を取り、max1つ追加して、部分文字列を取得します...

注：上記はでは機能しませんa = ['intersyate', 'intersxate', 'interstate', 'intersrate']が、これは次のようになります。

 >>> index = len(
         filter(lambda l: l[0] == l[1], 
             [ x for x in enumerate(
                 [i for i in range(min(map(len, a))) 
                     if len(set(map(lambda e: e[i], a))) == 1]
         )]))
 >>> a[0][:index]
 inters

score 2 · Accepted Answer

究極のパフォーマンスをあまり気にしないのであれば、それほど複雑ではないようです。

def common_substring(data)
  data.inject { |m, s| s[0,(0..m.length).find { |i| m[i] != s[i] }.to_i] }
end

インジェクトの便利な機能の1つは、配列の最初の要素が相互に作用している状態でプレシードする機能です。これにより、nilメモチェックが回避されます。

puts common_substring(%w[ interspecies interstelar interstate ]).inspect
# => "inters"
puts common_substring(%w[ feet feel feeble ]).inspect
# => "fee"
puts common_substring(%w[ fine firkin fail ]).inspect
# => "f"
puts common_substring(%w[ alpha bravo charlie ]).inspect
# => ""
puts common_substring(%w[ fork ]).inspect
# => "fork"
puts common_substring(%w[ fork forks ]).inspect
# => "fork"

更新：ゴルフがここでのゲームである場合、67人のキャラクター：

def f(d)d.inject{|m,s|s[0,(0..m.size).find{|i|m[i]!=s[i]}.to_i]}end

score 2 · Accepted Answer

これは、ルビーを除いて、RobertoBonvalletのソリューションと非常によく似ています。

chars = %w[interspecies interstelar interstate].map {|w| w.split('') }
chars[0].zip(*chars[1..-1]).map { |c| c.uniq }.take_while { |c| c.size == 1 }.join

最初の行は、各単語を文字の配列に置き換えます。次に、zipこのデータ構造を作成するために使用します。

[["i", "i", "i"], ["n", "n", "n"], ["t", "t", "t"], ...

mapこれをにuniq減らします[["i"],["n"],["t"], ...

take_whileサイズが1ではない文字が見つかるまで（すべての文字が同じではないことを意味します）、文字を配列から削除します。最後に、私はjoin彼らを一緒に戻します。

score 2 · Accepted Answer

受け入れられた解決策は壊れています（たとえば、のような文字列に対して返されaます['a', 'ba']）。indexOf(tem1) == -1修正は非常に簡単で、文字通り3文字（から）を変更するだけindexOf(tem1) != 0で、関数は期待どおりに機能します。

残念ながら、タイプミスを修正するために回答を編集しようとしたとき、SOは「編集は少なくとも6文字でなければならない」と私に言いました。名前付けと読みやすさを改善することで、これらの3文字よりも多く変更することができましたが、それは少し多すぎるように感じます。

したがって、以下は、kennebecのソリューションの修正および改善された（少なくとも私の観点からは）バージョンです。

function commonPrefix(words) {
  max_word = words.reduce(function(a, b) { return a > b ? a : b });
  prefix   = words.reduce(function(a, b) { return a > b ? b : a }); // min word

  while(max_word.indexOf(prefix) != 0) {
    prefix = prefix.slice(0, -1);
  }

  return prefix;
}

（jsFiddle上）

配列をソートしてからその最初と最後の要素をフェッチする代わりに、英数字のmax / minを見つけるためにreduceメソッド（JavaScript 1.8）を使用することに注意してください。

score 2 · Accepted Answer

これらの答えをすべての派手な関数型プログラミング、並べ替え、正規表現などで読んでいる間、私はただ考えました：Cの少しの問題は何ですか？それで、これは間抜けな見た目の小さなプログラムです。

#include <stdio.h>

int main (int argc, char *argv[])
{
  int i = -1, j, c;

  if (argc < 2)
    return 1;

  while (c = argv[1][++i])
    for (j = 2; j < argc; j++)
      if (argv[j][i] != c)
        goto out;

 out:
  printf("Longest common prefix: %.*s\n", i, argv[1]);
}

それをコンパイルし、文字列のリストをコマンドライン引数として実行してから、goto！を使用することに賛成してください。

score 1 · Accepted Answer

私は次のことをします：

配列の最初の文字列を最初の開始部分文字列とします。
配列の次の文字列を取得し、文字列の1つの終わりに達するか、不一致が見つかるまで文字を比較します。不一致が見つかった場合は、開始サブストリングを不一致が見つかった長さに減らします。
すべての文字列がテストされるまで、手順2を繰り返します。

JavaScriptの実装は次のとおりです。

var array = ["interspecies", "interstelar", "interstate"],
    prefix = array[0],
    len = prefix.length;
for (i=1; i<array.length; i++) {
    for (j=0, len=Math.min(len,array[j].length); j<len; j++) {
        if (prefix[j] != array[i][j]) {
            len = j;
            prefix = prefix.substr(0, len);
            break;
        }
    }
}

score 1 · Accepted Answer

Rubyで正規表現を使用するソリューションは次のとおりです。

def build_regex(string)
  arr = []
  arr << string.dup while string.chop!
  Regexp.new("^(#{arr.join("|")})")
end

def substring(first, *strings)
  strings.inject(first) do |accum, string|
    build_regex(accum).match(string)[0]
  end
end

score 1 · Accepted Answer

並べ替える代わりに、文字列の最小値と最大値を取得できます。

私にとって、コンピュータープログラムの優雅さは、スピードとシンプルさのバランスです。不必要な計算を行うべきではなく、その正しさを明らかにするのに十分単純でなければなりません。

ソートソリューションを「賢い」と呼ぶことはできますが、「エレガント」とは言えません。

score 1 · Accepted Answer

多くの場合、独自のライブラリを作成するのではなく、成熟したオープンソースライブラリを使用する方がエレガントです。次に、ニーズに完全に適合しない場合は、拡張または変更して改善し、それがライブラリに属するかどうかをコミュニティに判断させることができます。

diff-lcsは、最も一般的でない部分文字列に適したRubygemです。

score 1 · Accepted Answer

Javaでの私の解決策：

public static String compute(Collection<String> strings) {
    if(strings.isEmpty()) return "";
    Set<Character> v = new HashSet<Character>();
    int i = 0;
    try {
        while(true) {
            for(String s : strings) v.add(s.charAt(i));
            if(v.size() > 1) break;
            v.clear();
            i++;
        }
    } catch(StringIndexOutOfBoundsException ex) {}
    return strings.iterator().next().substring(0, i);
}

score 1 · Accepted Answer

楽しみのためだけにゴルフをしたJSソリューション：

w=["hello", "hell", "helen"];
c=w.reduce(function(p,c){
    for(r="",i=0;p[i]==c[i];r+=p[i],i++){}
    return r;
});

score 1 · Accepted Answer

これがルビーの効率的な解決策です。私は、最長のプレフィックスに繰り返し焦点を合わせるhi/lo推測ゲームの戦略のアイデアに基づいています。

私が間違っていれば誰かが私を訂正しますが、複雑さはO（n log n）だと思います。ここで、nは最短の文字列の長さであり、文字列の数は定数と見なされます。

def common(strings)
  lo = 0
  hi = strings.map(&:length).min - 1
  return '' if hi < lo

  guess, last_guess = lo, hi

  while guess != last_guess
    last_guess = guess
    guess = lo + ((hi - lo) / 2.0).ceil

    if strings.map { |s| s[0..guess] }.uniq.length == 1
      lo = guess
    else
      hi = guess
    end
  end

  strings.map { |s| s[0...guess] }.uniq.length == 1 ? strings.first[0...guess] : ''
end

そして、それが機能することを確認するものもあります。

>> common %w{ interspecies interstelar interstate }
=> "inters"

>> common %w{ dog dalmation }
=> "d"

>> common %w{ asdf qwerty }
=> ""

>> common ['', 'asdf']
=> ""

score 1 · Accepted Answer

楽しい代替Rubyソリューション：

def common_prefix(*strings)
  chars  = strings.map(&:chars)
  length = chars.first.zip( *chars[1..-1] ).index{ |a| a.uniq.length>1 }
  strings.first[0,length]
end

p common_prefix( 'foon', 'foost', 'forlorn' ) #=> "fo"
p common_prefix( 'foost', 'foobar', 'foon'  ) #=> "foo"
p common_prefix( 'a','b'  )                   #=> ""

chars = strings.sort_by(&:length).map(&:chars)最初の文字列が短いほど、によって作成される配列が短くなるため、を使用すると速度が向上する可能性がありますzip。ただし、速度を気にする場合は、このソリューションを使用しないでください。:)

score 0 · Accepted Answer

@Svanteのアルゴリズムに基づくルビーバージョン。私の最初のものの約3倍の速さで実行されます。

 def common_prefix set 
   i=0
   rest=set[1..-1]
   set[0].each_byte{|c|
     rest.each{|e|return set[0][0...i] if e[i]!=c}
     i+=1
   }
   set
 end

score 0 · Accepted Answer

これは決してエレガントではありませんが、簡潔にしたい場合は次のようにします。

ルビー、71文字

def f(a)b=a[0];b[0,(0..b.size).find{|n|a.any?{|i|i[0,n]!=b[0,n]}}-1]end

展開したい場合は、次のようになります。

def f(words)
  first_word = words[0];
  first_word[0, (0..(first_word.size)).find { |num_chars|
    words.any? { |word| word[0, num_chars] != first_word[0, num_chars] }
  } - 1]
end

score 0 · Accepted Answer

AShellyの優れた答えのJavascriptクローン。

FirefoxArray#reduceでのみサポートされているものが必要です。

var strings = ["interspecies", "intermediate", "interrogation"]
var sub = strings.reduce(function(l,r) { 
    while(l!=r.slice(0,l.length)) {  
        l = l.slice(0, -1);
    }
    return l;
});

score 0 · Accepted Answer

コードゴルフではありませんが、やや上品なものを求められており、再帰は楽しいと思いがちです。Java。

/** Recursively find the common prefix. */
public String findCommonPrefix(String[] strings) {

    int minLength = findMinLength(strings);

    if (isFirstCharacterSame(strings)) {
        return strings[0].charAt(0) + findCommonPrefix(removeFirstCharacter(strings));
    } else {
        return "";
    }
}

/** Get the minimum length of a string in strings[]. */
private int findMinLength(final String[] strings) {
    int length = strings[0].size();
    for (String string : strings) {
        if (string.size() < length) {
            length = string.size();
        }
    }
    return length;
}

/** Compare the first character of all strings. */
private boolean isFirstCharacterSame(String[] strings) {
    char c = string[0].charAt(0);
    for (String string : strings) {
        if (c != string.charAt(0)) return false;
    }

    return true;
}

/** Remove the first character of each string in the array, 
    and return a new array with the results. */
private String[] removeFirstCharacter(String[] source) {
    String[] result = new String[source.length];
    for (int i=0; i<result.length; i++) {
        result[i] = source[i].substring(1); 
    }
    return result;
}

score 0 · Accepted Answer

私のJavascriptソリューション：

IMOP、ソートの使用はトリッキーすぎます。私の解決策は、配列をループして文字ごとに比較することです。文字がマックされていない場合は文字列を返します。

これが私の解決策です：

var longestCommonPrefix = function(strs){
    if(strs.length < 1){
        return '';
    }

    var p = 0, i = 0, c = strs[0][0];

    while(p < strs[i].length && strs[i][p] === c){
        i++;
        if(i === strs.length){
            i = 0;
            p++;
            c = strs[0][p];
        }
    }

    return strs[0].substr(0, p);
};

score 0 · Accepted Answer

これがコードゴルフの試合に変わるリスクを認識して（またはそれが意図ですか？）、これが私の答えsedから別のSO質問にコピーされ、 36文字に短縮された私の解決策です（そのうち30文字は実際の表現です）。文字列（それぞれ別の行にある）は、標準の入力または追加の引数として渡されるファイルで提供されることを想定しています。sed

sed 'N;s/^\(.*\).*\n\1.*$/\1\n\1/;D'

シバン行にsedが含まれるスクリプトは、45文字の重さがあります。

#!/bin/sed -f
N;s/^\(.*\).*\n\1.*$/\1\n\1/;D

longestprefix「ヒアドキュメント」として提供される文字列を使用した、スクリプト（名前付き）のテスト実行：

$ ./longestprefix <<EOF
> interspecies
> interstelar
> interstate
> EOF
inters
$

score 0 · Accepted Answer

ルビー

require 'abbrev'

ar = ["interspecies", "interstelar", "interstate"]
ar.abbrev.keys.min_by(&:size).chop # => "inters"

文字列abbrevのセットを指定して、それらの文字列の明確な略語のセットを計算し、キーがすべての可能な略語であるハッシュを返します（値は完全な文字列です）。最短のキーから最後の文字を引いたものが共通のプレフィックスになります。。

javascript - 文字列のセットから最も長い共通の開始部分文字列を検索します

更新：私のお気に入りのソリューション

31 に答える 31

ルビー、71文字

Related

Reference