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
14
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 bound
          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
13
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 bound
          return false;
        if (words.get(i).charAt(j) != words.get(j).charAt(i))
          return false;
      }

    return true;
  }
}