algorithms/leetcode/422-ValidWordSquare.go at master · freewu/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
package main

// 422. Valid Word Square
// Given an array of strings words, return true if it forms a valid word square.
// A sequence of strings forms a valid word square
// if the kth row and column read the same string, where 0 <= k < max(numRows, numColumns).

// Example 1:
// <img src="https://assets.leetcode.com/uploads/2021/04/09/validsq1-grid.jpg" />
// Input: words = ["abcd","bnrt","crmy","dtye"]
// Output: true
// Explanation:
// The 1st row and 1st column both read "abcd".
// The 2nd row and 2nd column both read "bnrt".
// The 3rd row and 3rd column both read "crmy".
// The 4th row and 4th column both read "dtye".
// Therefore, it is a valid word square.

// Example 2:
// <img src="https://assets.leetcode.com/uploads/2021/04/09/validsq2-grid.jpg" />
// Input: words = ["abcd","bnrt","crm","dt"]
// Output: true
// Explanation:
// The 1st row and 1st column both read "abcd".
// The 2nd row and 2nd column both read "bnrt".
// The 3rd row and 3rd column both read "crm".
// The 4th row and 4th column both read "dt".
// Therefore, it is a valid word square.

// Example 3:
// <img src="https://assets.leetcode.com/uploads/2021/04/09/validsq3-grid.jpg" />
// Input: words = ["ball","area","read","lady"]
// Output: false
// Explanation:
// The 3rd row reads "read" while the 3rd column reads "lead".
// Therefore, it is NOT a valid word square.

// Constraints:
//     1 <= words.length <= 500
//     1 <= words[i].length <= 500
//     words[i] consists of only lowercase English letters.

import "fmt"

func validWordSquare(words []string) bool {
    l := len(words)
    for i := 0; i < l; i++ {
        for j := 0; j < len(words[i]); j++ {
            // 处理长度边界问题不够直接返回 false
            if j >= l || i >= len(words[j]) || words[i][j] != words[j][i] {
                return false
            }
        }
    }
    return true
}

func validWordSquare1(words []string) bool {
    for i := range words{
        for j := range words[i] {
            if  j >= len(words) || i >= len(words[j]) || words[i][j] != words[j][i] {
                return false
            }
        }
    }
    return true
}

func main() {
    // Example 1:
    // <img src="https://assets.leetcode.com/uploads/2021/04/09/validsq1-grid.jpg" />
    // Input: words = ["abcd","bnrt","crmy","dtye"]
    // Output: true
    // Explanation:
    // The 1st row and 1st column both read "abcd".
    // The 2nd row and 2nd column both read "bnrt".
    // The 3rd row and 3rd column both read "crmy".
    // The 4th row and 4th column both read "dtye".
    // Therefore, it is a valid word square.
    fmt.Println(validWordSquare([]string{"abcd","bnrt","crmy","dtye"})) // true
    // Example 2:
    // <img src="https://assets.leetcode.com/uploads/2021/04/09/validsq2-grid.jpg" />
    // Input: words = ["abcd","bnrt","crm","dt"]
    // Output: true
    // Explanation:
    // The 1st row and 1st column both read "abcd".
    // The 2nd row and 2nd column both read "bnrt".
    // The 3rd row and 3rd column both read "crm".
    // The 4th row and 4th column both read "dt".
    // Therefore, it is a valid word square.
    fmt.Println(validWordSquare([]string{"abcd","bnrt","crm","dt"})) // true
    // Example 3:
    // <img src="https://assets.leetcode.com/uploads/2021/04/09/validsq3-grid.jpg" />
    // Input: words = ["ball","area","read","lady"]
    // Output: false
    // Explanation:
    // The 3rd row reads "read" while the 3rd column reads "lead".
    // Therefore, it is NOT a valid word square.
    fmt.Println(validWordSquare([]string{"ball","area","read","lady"})) // false

    fmt.Println(validWordSquare([]string{"bluefrog","leetcode","freewu"})) // false

    fmt.Println(validWordSquare1([]string{"abcd","bnrt","crmy","dtye"})) // true
    fmt.Println(validWordSquare1([]string{"abcd","bnrt","crm","dt"})) // true
    fmt.Println(validWordSquare1([]string{"ball","area","read","lady"})) // false
    fmt.Println(validWordSquare1([]string{"bluefrog","leetcode","freewu"})) // false
}