arrays - 文字列の配列のすべての順列からの最長実行シーケンス

Question

Amazon の最近のインタビューから、次の質問を見つけました。それを解決する効果的な方法を見つけることができませんでした。
問題は次のとおりです。
文字列の配列が与えられた場合、配列内の文字列のすべての可能な順列の中から文字の最長実行シーケンスを見つける必要があります。

入力 :
ab
ba
aac
出力 :
a,3

注: 入力と出力のセットから、個々の文字列の並べ替えは行われないと思います。

誰かが助けてくれれば本当にありがたいです。ありがとう。

Answer 1

素敵な質問。非常に多くのコーナーケース。このインタビューの質問の要点は、あなたが何件のコーナーケースを思いつくかを見ることだと思います。

見逃していないことを願っています。

文字シーケンスがこの問題の解決策になるには、基本的に2つの方法があります。

1）それは内部の文字シーケンスです（例adddddddddddddddddb）

2）これは、接尾辞、その文字のみで構成される文字列のコレクション全体、および接頭辞の連結です。この場合、文字が同じ文字列の接尾辞と接頭辞である場合を含め、文字列を複数回使用することはできません。（同種の文字列の再発行を回避するには、接尾辞と接頭辞を厳密にする必要があります。つまり、文字列全体ではありません）。

ケース1は簡単です。単一の文字とシーケンスの長さ、および現在の文字とシーケンスの長さを覚えているだけです。文字列を読み取るときに、現在の文字/シーケンスの長さが最大値よりも長い場合は、最大値を置き換えます。結果に影響を与えないため、ケース2で実行された計算と競合することを心配する必要はありません。

ケース2はもっと多くの作業です。キャラクターごとに、いくつかのデータを保持する必要があります。アルファベットが小さい場合は、固定サイズの配列（アルファベットの文字ごとに1つのエントリ）を使用するか、文字のハッシュテーブルを使用できます。どちらもO(1)平均しています。処理する文字数は、すべての文字列の合計文字数を超えることはできないため、ハッシュテーブルのサイズ要件はと考えることができますO(N)。（実際、アルファベットのサイズによって制限されるため、固定サイズの配列と同様に、ストレージ要件は技術的O(1)には異なりますが、たとえばUnicodeの場合、定数はかなり大きくなります。）

では、どのようなデータが必要ですか？1文字の繰り返しである文字列は簡単です。これらの文字列の全長が必要です。したがって、そのような文字列を見つけるたびに、その長さを文字ごとのデータのエントリの全長メンバーに追加できます。

（厳密な）接尾辞と接頭辞の場合、それぞれの最大長を維持するだけでよいようです。しかし、プレフィックスとサフィックスのシーケンスが同じ文字であり、両方のシーケンスが以前に処理したものよりも長い文字列に遭遇した場合はどうなるでしょうか。文字列をサフィックスとプレフィックスの両方として使用することはできません。幸い、簡単な答えがあります。maximum_prefix、maximum_suffix、maximum_sumの3つの値を保持します。単語を読んだ後にテーブルを更新していて、同じ文字がプレフィックスとサフィックスの両方であることが判明した場合、次のように3つの値を更新します。

maximum_sum = max(maximum_sum, 
                  prefix_length + maximum_suffix,
                  suffix_length + maximum_prefix)
maximum_prefix = max(maximum_prefix, prefix_length)
maximum_suffix = max(maximum_suffix, suffix_length)

上記の擬似コードは、prefix_lengthまたはsuffix_lengthのいずれかが0の場合、（少し無駄な場合でも）問題なく機能することに注意してください。

つまり、文字ごとに合計4つの値になりますhomogenous_length, maximum_sum, maximum_prefix, maximum_suffix。homogenous_length + maximum_sumスキャンの最後に、最も優れたキャラクターを見つける必要があります。これは、指標表をスキャンするだけで実行できます。

合計処理時間はO(1)、文字ごと（最初のスキャンの場合）です。つまり、 O(N)（N問題の文字の総数に加えO(max(N, |A|))て、文字テーブルの最後のスキャンの場合（|A|アルファベットのサイズ）です。つまり、O(N)。スペース要件は上記のとおりです。

Answer 2

ステップ 1 : 4 つのテーブルは長さ 26 で維持する必要があります --最初のテーブルは文字列内の最長のプレフィックスの長さを追跡します --2 番目のテーブルは文字列内の最長のサフィックスの長さを追跡します --3 番目のテーブルは追跡します全体が特定の文字で構成される文字列の合計の長さ -- 4 番目は、中央の最も長い文字を追跡します。

ステップ 2: -- 0 ～ 26 のループを実行し、first[i]+second[i]+ third[i] を加算して sum[i] に格納 --sum[i] と 4 番目のテーブルの最大要素を見つける。--index はアルファベット (0 は A) で、最大要素は長さです

#include <stdio.h>
#include <string.h>
#include <ctype.h>


int pre[26],su[26],single[26],middle[26],sum[26];
int getlength(char str[][10])
{
int i,j,n=3,counter=0,max=-1,index;
char c,p;
for(j=0;j<n;j++)
{
 for(i=0;i<strlen(str[j]);i++)
{
 if(i==0) 
{
  c=str[j][i];
  counter++;
  continue;
  }
    else if(i==strlen(str[j])-1&&c == str[j][i])
  {
    counter =0;
    break;
   }
  else
  {
    if(c == str[j][i])
    counter++;
    else 
     break;
   }

  }
    if(pre[toupper(c)-65]<counter)
      pre[toupper(c)-65]=counter;
      counter=0;
  }
for(j=0;j<n;j++)
{
  for(i=strlen(str[j])-1;i>=0;i--)
  {
    if(i==strlen(str[j])-1)
    {
     c=str[j][i];
      counter++;
      continue;
     }
   else if(i==0&&c == str[j][i])
   {
     counter =0;
     break;
   }
   else
   {
     if(c == str[j][i])
     counter++;
   else
    break;
   }

} 
if(su[toupper(c)-65]<counter)
 su[toupper(c)-65]=counter;
 counter=0;
 }

for(j=0;j<n;j++)
{
for(i=strlen(str[j])-1;i>=0;i--)
  {
  if(i==strlen(str[j])-1)
  {
  c=str[j][i];
  counter++;
  continue;
  }
 else
{
 if(c == str[j][i])
 counter++;
 else
 {
counter=0;   
 break;
 }
}

 }
    if(single[toupper(c)-65]<counter)
      single[toupper(c)-65]=counter;
      counter=0;
}
counter=0;
for(j=0;j<n;j++)
{
  for(i=1;i<strlen(str[j])-1;i++)
{
if(i==1)
 {
   c=str[j][i];

   counter++;
 }
  else
 {
   if(c == str[j][i])
 {

   counter++;
  }
 else
 {
 if(middle[toupper(c)-65]<counter)
   middle[toupper(c)-65]=counter;
   counter=1;
   c=str[j][i];
  }

} 
}
 counter=0;
}

 for(i=0;i<26;i++)
{
  sum[i]=pre[i]+su[i]+single[i];
   if(sum[i]>max)
 {
   max=sum[i];
   index=i;
  }
}

for(i=0;i<26;i++)
{

if(middle[i]>max)
{
max=middle[i];
index=i;
}
  }
   printf("\n length %d index %d",max,index);


  }
void main()
{
char arr[3][10]={"bbbb","dccccccar","vaa"};
getlength(arr);
}

Answer 3

これは私の単純な Ruby 実装です。私はそれをどのように推論し、実装したかを説明しようとします。

Ruby では文字列は列挙可能ではないため、Ruby は Python のように文字列を直接列挙することはできません。それでstr.chars.to_a解決です。文字列を文字の配列に変換します。

私の計画は、各文字列で文字が出現する回数を数えることでした。["ab", "ba", "ccc"]になり[{"a"=>1, "b"=>1}, {"b"=>1, "a"=>1}, {"c"=>3}]ます。次に、連続するハッシュ/辞書の各ペアの出現回数を追加します。この例では、結果は になり[{"a"=>2, "b"=>2}, {"b"=>1, "a"=>1, "c"=>3}]ます。このハッシュの配列の最大値は、最も長く実行されているシーケンスを表します。

問題は、同じ文字を何度も含む文字列がこのアルゴリズムを破綻させることです。これに対する私の解決策は、これらの種類の文字列をチェックし、その文字列にそのような文字が含まれている場合は、これらを次の文字列と連結することです。arr_of_chararr.eachこれはメソッド内で実装されmax_running_sequenceます。

Hash#merge配列に要素が 1 つしかない特殊なケースを除いて、ペアワイズ加算はブロックで実装されます。

最後に、ハッシュの配列をスキャンして最大値を探します。

class Sequence_tester
  def self.max_running_sequence(arr_of_chararr)
    reduced = []
    all_same_chars = []

    arr_of_chararr.each do |str|
      arr = str.chars.to_a
      if arr.all? {|c| c == arr.first}
        all_same_chars += arr
      else
        if !all_same_chars.empty?
          if arr.any? {|c| c == all_same_chars.first}
            arr += all_same_chars
          else
            reduced << count_char_occurrences(all_same_chars)
          end
        end
        reduced << count_char_occurrences(arr)
        all_same_chars.clear
      end
    end

    if !all_same_chars.empty?
      reduced << count_char_occurrences(all_same_chars)
    end

    max_seqs = reduced
    if reduced.length > 1
      max_seqs = reduced.each_cons(2).map do |pair|
        pair.first.merge(pair.last) {|key, oldval, newval| oldval + newval}
      end
    end

    longest_seq = max_seqs.map {|h| h.max_by {|kv| kv[1]} }.max_by {|a| a[1]}
  end

  def self.count_char_occurrences(arr)
    arr.each_with_object(Hash.new(0)) {|o, h| h[o] += 1}
  end
end

input = ["a", "b", "c"]
res = Sequence_tester.max_running_sequence(input)
puts "#{res.first},#{res.last}"
input = ["abc", "abb", "abc"]
res = Sequence_tester.max_running_sequence(input)
puts "#{res.first},#{res.last}"
input = ["ab", "ba", "ccc"]
res = Sequence_tester.max_running_sequence(input)
puts "#{res.first},#{res.last}"
input = ["ada", "dd", "dd", "eedd"]
res = Sequence_tester.max_running_sequence(input)
puts "#{res.first},#{res.last}"

出力:
a、1
b、3
c、3
d、7

Answer 4

    #include <iostream>

using namespace std;

class alphabet
{
      string str;
      int chars[26];

public:
       alphabet()
       {
                 for(int i=0; i < 26 ; i++)
                         chars[i] = 0;

       }

       void initialize(string s)
       {
            str = s;
            for(int pos=0 ; pos < s.length(); pos++)
                         chars[s[pos]-'a']++;
       }

       int getCount(int i)
       {
           return chars[i];
       }
};

int main()
{
    int n=3;
    alphabet *arr = new alphabet[n];
    arr[0].initialize("varun");
    arr[1].initialize("ritl");
    arr[2].initialize("hello");
    int Max =0;
    char MaxChar = ' ';
    for(int i=0; i<n-1 ; i++)
    {
            for(int j=0; j<26; j++)
            {
                    int m = arr[i].getCount(j)+ arr[i+1].getCount(j);
                    if(m > Max)
                    {
                         Max = m;
                         MaxChar = char('a' + j);
                    }
            }
    }
    cout<<"Max Char = "<<MaxChar<<" "<<Max<<" times";
    system("pause");    
}

Answer 5

そのためにハッシュマップを使用できます。最も遅いアルゴリズムは、文字列ごとに文字カウンターのマップを作成し、最大値を見つけることです。

より高度なアルゴリズムも知りたい