Skip to content

422. Valid Word Square

  • Time: $O(\Sigma |\texttt{words[i]}|)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
 public:
  bool validWordSquare(vector<string>& words) {
    for (int i = 0; i < words.size(); ++i)
      for (int j = 0; j < words[i].size(); ++j) {
        if (words.size() <= j || words[j].size() <= i)  // out-of-bounds
          return false;
        if (words[i][j] != words[j][i])
          return false;
      }
    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
  public boolean validWordSquare(List<String> words) {
    for (int i = 0; i < words.size(); ++i)
      for (int j = 0; j < words.get(i).length(); ++j) {
        if (words.size() <= j || words.get(j).length() <= i) // out-of-bounds
          return false;
        if (words.get(i).charAt(j) != words.get(j).charAt(i))
          return false;
      }
    return true;
  }
}

1
2
3
4
5
6
7
8
9
class Solution:
  def validWordSquare(self, words: List[str]) -> bool:
    for i, word in enumerate(words):
      for j, c in enumerate(word):
        if len(words) <= j or len(words[j]) <= i:  # out-of-bounds
          return False
        if c != words[j][i]:
          return False
    return True