422. Valid Word Square

题目:

Given a sequence of words, check whether it forms a valid word square.

A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).

Note:

  1. The number of words given is at least 1 and does not exceed 500.
  2. Word length will be at least 1 and does not exceed 500.
  3. Each word contains only lowercase English alphabet a-z.

Example 1:

Input:
[
  "abcd",
  "bnrt",
  "crmy",
  "dtye"
]

Output:
true

Explanation:
The first row and first column both read "abcd".
The second row and second column both read "bnrt".
The third row and third column both read "crmy".
The fourth row and fourth column both read "dtye".

Therefore, it is a valid word square.

Example 2:

Input:
[
  "abcd",
  "bnrt",
  "crm",
  "dt"
]

Output:
true

Explanation:
The first row and first column both read "abcd".
The second row and second column both read "bnrt".
The third row and third column both read "crm".
The fourth row and fourth column both read "dt".

Therefore, it is a valid word square.

Example 3:

Input:
[
  "ball",
  "area",
  "read",
  "lady"
]

Output:
false

Explanation:
The third row reads "read" while the third column reads "lead".

Therefore, it is NOT a valid word square.

链接:https://leetcode.com/problems/valid-word-square/#/description

3/25/2017

注意:

只看给的几个例子是不行的,要把题目读全,

A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).

说实话这道题是蒙对的,performance居然还不错26ms

 1 public class Solution {
 2     public boolean validWordSquare(List<String> words) {
 3         int rowLength = words.size();
 4         for (String s: words) {
 5             if (s.length() > rowLength) return false;
 6         }
 7         for (int i = 0; i < rowLength; i++) {
 8             for (int j = i; j < rowLength; j++) {
 9                 if (words.get(i).length() > j && words.get(j).length() > i && words.get(i).charAt(j) == words.get(j).charAt(i)) ;
10                 else if (words.get(i).length() <= j && words.get(j).length() <= i) ;
11                 else return false;
12             }
13         }
14         return true;
15     }
16 }

别人类似的算法

不同的是j的范围是根据当前i行的长度来的,判断条件里前两个是为了保证charAt()函数安全。

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

一行Python

The map(None, ...) transposes the "matrix", filling missing spots with None.

1 def validWordSquare(self, words):
2     t = map(None, *words)
3     return t == map(None, *t)

更多讨论:

https://discuss.leetcode.com/category/551/valid-word-square

时间: 03-25

422. Valid Word Square的相关文章

LeetCode Valid Word Square

原题链接在这里:https://leetcode.com/problems/valid-word-square/ 题目: Given a sequence of words, check whether it forms a valid word square. A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(

[LeetCode] Valid Word Square 验证单词平方

Given a sequence of words, check whether it forms a valid word square. A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤k < max(numRows, numColumns). Note: The number of words given is at le

69. Sqrt(x) &amp;&amp; 367. Valid Perfect Square

69. Sqrt(x) Implement int sqrt(int x). Compute and return the square root of x. Hide Tags Binary Search Math Hide Similar Problems (M) Pow(x, n) (M) Valid Perfect Square Time Limit Exceed Solution if start from 0. public class Solution { public int m

408. Valid Word Abbreviation

Given a non-empty string s and an abbreviation abbr, return whether the string matches with the given abbreviation. A string such as "word" contains only the following valid abbreviations: ["word", "1ord", "w1rd", &

Valid Word Abbreviation Leetcode

Given a non-empty string s and an abbreviation abbr, return whether the string matches with the given abbreviation. A string such as "word" contains only the following valid abbreviations: ["word", "1ord", "w1rd", &

[leetcode] 367. Valid Perfect Square

Given a positive integer num, write a function which returns True if num is a perfect square else False. Note: Do not use any built-in library function such as sqrt. Example 1: Input: 16 Returns: True Example 2: Input: 14 Returns: False 使用二分查找寻找input

【leetcode】367. Valid Perfect Square]

题目描述: Given a positive integer num, write a function which returns True if num is a perfect square else False. 解题分析: 这种找数字的题一般都用类似与二分查找的算法.需要注意的是比较平方和时考虑到integer溢出的情况.所以这个结果是要用Long类型保存.由此到来的改变是判断相等时要用“equals()”方法,而不是“==”. 实现代码: 1 public class Solutio

367. Valid Perfect Square

题目: Given a positive integer num, write a function which returns True if num is a perfect square else False. Note: Do not use any built-in library function such as sqrt. Example 1: Input: 16 Returns: True Example 2: Input: 14 Returns: False 链接: https

Valid Perfect Square

Given a positive integer num, write a function which returns True if num is a perfect square else False. Note: Do not use any built-in library function such as sqrt. Example 1: Input: 16 Returns: True Example 2: Input: 14 Returns: False 1 public clas