Лучший способ обнаружить сгруппированные слова

Question

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

С учетом vector<string> вернуть количество сгруппированных слов.

Например:

{"ab", "aa", "aca", "ba", "bb"}

возврат 4 .

Здесь "aca" не является сгруппированным словом.

Мое быстрое и грязное решение:

int howMany(vector <string> words) {
  int ans = 0;
  for (int i = 0; i < words.size(); i++) {
       bool grouped = true;
  for (int j = 0; j < words[i].size()-1; j++)
      if (words[i][j] != words[i][j+1])
         for (int k = j+1; k < words[i].size(); k++)
           if (words[i][j] == words[i][k])
              grouped = false;
           if (grouped) ans++;
       }
   return ans;
 }

Я хочу лучший алгоритм для той же проблемы.

Answer 1

Попробуйте следующее:

bool isGrouped( string const& str )
{
  set<char> foundCharacters;
  char currentCharacter='\0';

  for( int i = 0 ; i < str.size() ; ++i )
  {
    char c = str[i];
    if( c != currentCharacter )
    {
      if( foundCharacters.insert(c).second )
      {
        currentCharacter = c;
      }
      else
      {
        return false;
      }
    }
  }
  return true;
}

Answer 2

Вы можете использовать какой-нибудь набор (предпочтительно с O (1) вставкой и временем поиска).

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

Answer 3

Рассматривая только одно слово, вот деструктивный алгоритм O (n log n):

std::string::iterator unq_end = std::unique( word.begin(), word.end() );
std::sort( word.begin(), unq_end );
return std::unique( word.begin(), unq_end ) == unq_end;

Редактировать: Первый вызов unique уменьшает количество последовательных букв до отдельных букв. Призыв к sort группирует одинаковые буквы. Второй вызов unique проверяет, образовались ли sort какие-либо новые группы последовательных букв. Если это так, то слово не должно быть сгруппировано.

Преимущество перед другими опубликовано в том, что он не требует хранения - хотя это не так много преимуществ.

Вот простая версия альтернативного алгоритма, также требующая только O (1) хранилища (и да, также проверенная):

if ( word.empty() ) return true;
bitset<CHAR_MAX+1> symbols;
for ( string::const_iterator it = word.begin() + 1; it != word.end(); ++ it ) {
    if ( it[0] == it[-1] ) continue;
    if ( symbols[ it[0] ] ) return false;
    symbols[ it[-1] ] = true;
}
return ! symbols[ * word.rbegin() ];

Обратите внимание, что вам потребуются незначительные изменения для работы с символами вне ASCII. bitset исходит из заголовка <bitset>.

Answer 4

Вот многострочное, подробное регулярное выражение для соответствия ошибкам:

    (?:         # Non capturing group of ...
      (\S)\1*   # One or more of any non space character (capured).
    )
    (?!         # Then a position without
      \1        # ... the captured character
    ).+         # ... at least once.
    \1          # Followed by the captured character.

или меньше:

"(?:(\S)\1*)(?!\1).+\1"

Я просто предполагаю, что в C ++ есть реализация regexp, которая работает, она работает в Python и должна работать также в Perl и Ruby.

Answer 5

    public static Boolean isGrouped( String input )
    {
        char[] c = input.ToCharArray();
        int pointer = 0;
        while ( pointer < c.Length - 1 )
        {
            char current = c[pointer];
            char next = c[++ pointer];
            if (   next != current && 
                 ( next + 1 ) != current && 
                 ( next - 1 ) == current 
               ) return false; 
        }
        return true;
    }

(C #, но применяется принцип)

Answer 6

Вот способ с двумя циклами на слово, за исключением того, что один из циклов не до длины слова, а до размера алфавита. В худшем случае O (N L s), где N = количество слов, L = длина слова, s = размер алфавита:

for each word wrd:
{
  for each character c in the alphabet:
  {
    for each letter i in wrd:
    {
      let poz = last position of character c in wrd. initially poz = -1
      if ( poz == -1 && c == wrd[i] )
         poz = i;
      else if ( c == wrd[i] && poz != i - 1 )
         // definitely not grouped, as it's separated by at least one letter from the prev sequence
    }
  }
  // grouped if the above else condition never executed
}

в основном проверяет, не существует ли каждая буква в алфавите или она присутствует только в одной подстроке этих букв.

Answer 7

Это может работать в два цикла на слово:

1) Зацикливайте слово, подсчитывая количество появляющихся символов. (Для этого потребуется дополнительное хранилище, максимально равное длине строки - возможно, какой-то хэш.)

2) Зацикливание слова подсчитывает количество раз, когда символ n отличается от символа n + 1.

Если эти два значения не отличаются ровно на одно, слово не группируется.