10ms java solution beating more than 90%


  • 0
    Y

    The idea is that, the diagonal doesn't matter - replace x with anything and the square would still be valid.

    x  a  b  c  d
    a  x  e  f  h
    b  e  x  g  i
    c  f  g  x  j
    d  h  i  j  x
    

    So let's only check items symmetric along the diagonal, also be careful of the invalid cases (words can't be longer than the first word):

    public class Solution {
        // the diagonal doesn't matter
        public boolean validWordSquare(List<String> words) {
            int m = words.size(), n = words.get(0).length();
            if (m!=n) return false;
            for (int i=1; i<m; i++) {
                if (m < words.get(i).length()) return false;
                for (int j=0; j<i; j++) {
                    if (!isSame(words, i, j)) return false;
                }
            }
            return true;
        }
        private boolean isSame(List<String> words, int i, int j) {
            String a = words.get(i);
            char ac = j < a.length() ? a.charAt(j) : ' ';
            if (j >= words.size()) return false;
            String b = words.get(j);
            char bc = i < b.length() ? b.charAt(i) : ' ';
            return ac == bc;
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.