Блог

По-видимому, это был вопрос, который был задан моему другу из Google. Вопрос в том, что, учитывая четыре слова из 4 букв, определите, образуют ли они квадрат слова. Затем разверните его, чтобы его можно было решить для любых n слов из n букв. Примером квадрата слова может быть:

 C A T S
A B E O
T E L M
S O M E
  

Самый быстрый способ, который мы могли придумать, это O (n!) для проверки всех возможных перестановок конфигураций слов, затем O (n) для проверки, образует ли он квадрат слова, что можно сделать, проверив, равна ли одна сторона диагоналей другой.

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

Вот реализация Python, которая использует коллекции.Класс счетчика вместо мультимножества.

 from collections import Counter

def word_square(words):
    words = list(words)
    n = len(words)
    assert all(len(w) == n for w in words)

    result = []

    for i in range(n):
        letters = Counter(w[i] for w in words)
        match = next((w for w in words if Counter(w[i:]) == letters), None)

        if not match:
            return None

        words.remove(match)
        result.append(match)

    return result
  

Это решение, если я не ошибаюсь, является O(n^3) , что не очень хорошо, но это улучшение по сравнению с O(n!) .

Это самый эффективный способ, о котором я могу думать:

 const validWordSquare = (words) => {
  if(words.length > 0) {
    let firstRow = words[0]
    if(firstRow.length !== words.length) {
      return false
    }

    for(let i = 0; i < firstRow.length; i  ) {
      let verticalWord = ''
      for(let j = 0; j < words.length; j  ) {
        verticalWord  = words[j][i]
      }
      if(verticalWord !== words[i]) {
        return false
      }
    }
    return true
  }
  return false
}
  

(Это алгоритм, который вы затем использовали бы для создания программы. Это было бы очень легко сделать в программе, но, очевидно, если бы человек смог это нарисовать, он смог бы быстро увидеть, так ли это. Если хотите, я мог бы написать вам Java-программу, которая сделает это.)

1. Я бы создал 2D-массив из первых букв каждого слова, находящихся в первом столбце, а первая строка состоит из первого слова.

    C A T S
   A B E O
   T E L M
   S O M E
     

2. Затем проверьте, равен ли первый столбец первому слову, второй столбец равен второму слову и так далее. (Поскольку первая строка буквально является первым словом, проверка того, равен ли первый столбец первому слову, в основном проверяет, равна ли первая строка первому столбцу.)

Это похоже на вопрос о транспонировании матрицы. Итак, если исходная матрица и ее транспонирование равны, то она образует квадрат слова,