The improved java solution with detailed explaination(beats 96%)


  • 0
    L

    This question is easy but two things worth attention.

    1. we can only search for the left bottom of the matrix.
      However , notice that we have to make sure although everything in the left bottom part have its counterpart in the right up part, there is no extra elements in the right up part. this is why we need to calculate the length of each string.
    2. we can use the try / catch statement to avoid trivial checking for the safety problem.
    public class Solution {
        public boolean validWordSquare(List<String> words) {
            if (words.size() == 0) return true;
            if (words.get(0).length() != words.size()) return false;
            int[] lenOfString = new int[words.size()];
            
            for (int i = 0; i < words.size(); i++) {
                //we can only check left bottom part of the matrix.
                for (int j = Math.min(words.get(i).length() - 1, i - 1); j >= 0; j--) {
                    try {  //using the exception you can save lots of time to ensure the safe problem.
                        if (words.get(i).charAt(j) != words.get(j).charAt(i)) {
                            return false;
                        }
                        lenOfString[j]++;
                    }  catch (Exception e) {
                        return false;
                    }  
                }
            }
            
            for (int i = 0; i < words.size(); i++) {
                int temp = (words.get(i).length() - i - 1);
                if (lenOfString[i] != temp && temp >= 0) {
                    return false; 
                }
                
            }
            
            return true;
        }
    
    }
    

Log in to reply
 

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