Java O(n) time no extra space 26ms Solution with explaination


  • -1
    W

    The idea is checking whether a char matrix is symmetric. Since List accesses take O(1), there is no need to create extra char[][] to store all the chars individually.

    I start by parsing the first row and first column, for the second row and column, we can start index from 1 since the first element has already been compared.
    '''
    public class Solution {
    public boolean validWordSquare(List<String> words) {
    // i stands for the starting position of each iteration
    for(int i = 0; i < words.size(); i++){
    // Check whether one row is longer than all possible column
    if(words.size() < words.get(i).length()) return false;

            // Check whether one row is shorter than the column
            if(words.get(i).length() < words.size() && words.get(words.get(i).length()).length() > i) return false;
            for(int j = 0; i + j < words.get(i).length(); j++){
                // Check whether one row is longer than the actual column
                if(words.get(j+i).length() <= i) return false;
                
                // Check whether corresponding chars are the same
                if(words.get(i).charAt(i+j) != words.get(j+i).charAt(i)) return false;
            }
        }
        return true;
    }
    

    }
    '''


Log in to reply
 

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