[Python/Java] O(mn/2) time, O(1) space


  • 0

    Only traverse half of the matrix. Compare the lower-left part with the upper-right. Ignore the diagonal characters.

    alt text

    class Solution(object):
        def validWordSquare(self, words):
            """
            :type words: List[str]
            :rtype: bool
            """
            rows = len(words)
            for i, word in enumerate(words):
                cols = len(word)
                if cols > rows:
                    return False
                for j in xrange(i + 1, rows):
                    a = word[j] if j < cols else ''
                    b = words[j][i] if i < len(words[j]) else ''
                    if a != b:
                        return False
            return True
    
    public class Solution {
        public boolean validWordSquare(List<String> words) {
            int rows = words.size();
            for (int i = 0; i < rows; i++) {
                String word = words.get(i);
                int cols = word.length();
                if (cols > rows) return false;
                for (int j = i + 1; j < rows; j++) {
                    char a = j < cols ? word.charAt(j) : ' ';
                    char b = i < words.get(j).length() ? words.get(j).charAt(i) : ' ';
                    if (a != b) return false;
                }
            }
            return true;
        }
    }
    

Log in to reply
 

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