import javafx.util.Pair;

import java.util.*;

class LadderLength {

public int ladderLength(String beginWord, String endWord, List<String> wordList) {

// Since all words are of same length.

int L = beginWord.length();

// Dictionary to hold combination of words that can be formed,

// from any given word. By changing one letter at a time.

Map<String, List<String>> allComboDict = new HashMap<>();

wordList.forEach(

word -> {

for (int i = 0; i < L; i++) {

// Key is the generic word

// Value is a list of words which have the same intermediate generic word.

String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);

List<String> transformations = allComboDict.getOrDefault(newWord, new ArrayList<>());

transformations.add(word);

allComboDict.put(newWord, transformations);

}

});

// Queue for BFS

Queue<Pair<String, Integer>> Q = new LinkedList<>();

Q.add(new Pair(beginWord, 1));

// Visited to make sure we don't repeat processing same word.

Map<String, Boolean> visited = new HashMap<>();

visited.put(beginWord, true);

while (!Q.isEmpty()) {

Pair<String, Integer> node = Q.remove();

String word = node.getKey();

int level = node.getValue();

for (int i = 0; i < L; i++) {

// Intermediate words for current word

String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);

// Next states are all the words which share the same intermediate state.

for (String adjacentWord : allComboDict.getOrDefault(newWord, new ArrayList<>())) {

// If at any point if we find what we are looking for

// i.e. the end word - we can return with the answer.

if (adjacentWord.equals(endWord)) {

return level + 1;

}

// Otherwise, add it to the BFS Queue. Also mark it visited

if (!visited.containsKey(adjacentWord)) {

visited.put(adjacentWord, true);

Q.add(new Pair(adjacentWord, level + 1));

}

}

}

}

return 0;

}

}

import java.util.HashMap;

class ValidSudoku {

public boolean isValidSudoku(char[][] board) {

// init data

HashMap<Integer, Integer>[] rows = new HashMap[9];

HashMap<Integer, Integer> [] columns = new HashMap[9];

HashMap<Integer, Integer> [] boxes = new HashMap[9];

for (int i = 0; i < 9; i++) {

rows[i] = new HashMap<Integer, Integer>();

columns[i] = new HashMap<Integer, Integer>();

boxes[i] = new HashMap<Integer, Integer>();

}

// validate a board

for (int i = 0; i < 9; i++) {

for (int j = 0; j < 9; j++) {

char num = board[i][j];

if (num != '.') {

int n = (int)num;

int box_index = (i / 3 ) * 3 + j / 3;

// keep the current cell value

rows[i].put(n, rows[i].getOrDefault(n, 0) + 1);

columns[j].put(n, columns[j].getOrDefault(n, 0) + 1);

boxes[box_index].put(n, boxes[box_index].getOrDefault(n, 0) + 1);

// check if this value has been already seen before

if (rows[i].get(n) > 1 || columns[j].get(n) > 1 || boxes[box_index].get(n) > 1)

return false;

}

}

}

return true;

}

}