ValidWordSquare.java

package string;
import java.util.*;

/**
 * Created by gouthamvidyapradhan on 04/06/2019 Given a sequence of words, check whether it forms a
 * valid word square.
 *
 * <p>A sequence of words forms a valid word square if the kth row and column read the exact same
 * string, where 0 ≤ k < max(numRows, numColumns).
 *
 * <p>Note: The number of words given is at least 1 and does not exceed 500. Word length will be at
 * least 1 and does not exceed 500. Each word contains only lowercase English alphabet a-z. Example
 * 1:
 *
 * <p>Input: [ "abcd", "bnrt", "crmy", "dtye" ]
 *
 * <p>Output: true
 *
 * <p>Explanation: The first row and first column both read "abcd". The second row and second column
 * both read "bnrt". The third row and third column both read "crmy". The fourth row and fourth
 * column both read "dtye".
 *
 * <p>Therefore, it is a valid word square. Example 2:
 *
 * <p>Input: [ "abcd", "bnrt", "crm", "dt" ]
 *
 * <p>Output: true
 *
 * <p>Explanation: The first row and first column both read "abcd". The second row and second column
 * both read "bnrt". The third row and third column both read "crm". The fourth row and fourth
 * column both read "dt".
 *
 * <p>Therefore, it is a valid word square. Example 3:
 *
 * <p>Input: [ "ball", "area", "read", "lady" ]
 *
 * <p>Output: false
 *
 * <p>Explanation: The third row reads "read" while the third column reads "lead".
 *
 * <p>Therefore, it is NOT a valid word square.
 *
 * Solution: O(N x M) where N is number of words and M is max length of a string.
 * Save strings for each column and each row in a array and compare them both.
 */
public class ValidWordSquare {
  public static void main(String[] args) {
      List<String> arr = Arrays.asList("abcd", "bnrt", "crmy", "dtye");
    System.out.println(new ValidWordSquare().validWordSquare(arr));
  }

    public boolean validWordSquare(List<String> words) {
      List<String> newList = new ArrayList<>();
      int max = 0;
      for(int i = 0; i < words.size(); i ++){
          max = Math.max(max, words.get(i).length());
      }


      for(int i = 0; i < max; i ++){
          StringBuilder sb = new StringBuilder();
          for(String w : words){
              if(i < w.length()){
                  sb.append(w.charAt(i));
              } else break;
          }
          newList.add(sb.toString());
      }

      if(words.size() != newList.size()) return false;

      for(int i = 0, l = words.size(); i < l; i ++){
          if(!words.get(i).equals(newList.get(i))) return false;
      }
      return true;
    }
}