• Tweet

• Tweet

leetcode – Add Search Word – Data structure design in cpp

Question Solution

leetcode – Add Search Word – Data structure design in cpp

Design a data structure that supports the following two operations:

void addWord(word)

bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord(“bad”)

addWord(“dad”)

addWord(“mad”)

search(“pad”) -> false

search(“bad”) -> true

search(“.ad”) -> true

search(“b..”) -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

Following is the class implementing a trie data structure.
class TrieNode{
public:
char c;
unordered_map<char, TrieNode*> children ;
bool isLeaf;
TrieNode(char c){
this->c = c;
}
TrieNode() : isLeaf(false), children() { }
};
class WordDictionary {
private :
TrieNode* root;
public:
WordDictionary(){
root = new TrieNode();
}
// Adds a word into the data structure.
void addWord(string word) {
TrieNode* child=root;
for(int i=0; i<word.length(); i++){
char c = word[i];
if(child->children.count(c)==0)
child->children[c]=new TrieNode();
child =child->children[c];
}
child->isLeaf = true;
}
// Returns if the word is in the data structure. A word could
// contain the dot character ‘.’ to represent any one letter.
bool search(string word) {
return dfsSearch(root->children, word, 0);
}
bool dfsSearch(unordered_map<char, TrieNode*>children, string word, int start) {
if(start == word.length()){
if(children.size()==0)
return true;
else
return false;
}
char c = word[start];
if(children.find(c) != children.end()){
if(start == word.length()-1 && children[c]->isLeaf){
return true;
}
return dfsSearch(children[c]->children, word, start+1);
}else if(c == ‘.’){
bool result = false;
unordered_map<char, TrieNode*>::iterator itr=children.begin();
for(; itr!= children.end();itr++){
if(start == word.length()-1 && (*itr).second->isLeaf){
return true;
}

//if any path is true, set result to be true;
if(dfsSearch((*itr).second->children, word, start+1)){
result = true;
}
}
return result;
}else{
return false;
}
}
};

Cut Off Trees for Golf Event

You are asked to cut off trees in a forest for a golf event. The forest is represented as a non-negative 2D map, in this map:

1. 0 represents the obstacle can’t be reached.
2. 1 represents the ground can be walked through.
3. The place with number bigger than 1 represents a tree can be walked through, and this positive number represents the tree’s height.

You are asked to cut off all the trees in this forest in the order of tree’s height – always cut off the tree with lowest height first. And after cutting, the original place has the tree will become a grass (value 1).

You will start from the point (0, 0) and you should output the minimum steps you need to walk to cut off all the trees. If you can’t cut off all the trees, output -1 in that situation.

You are guaranteed that no two trees have the same height and there is at least one tree needs to be cut off.

Example 1:

<b>Input:</b> 
[
 [1,2,3],
 [0,0,4],
 [7,6,5]
]
<b>Output:</b> 6

Example 2:

<b>Input:</b> 
[
 [1,2,3],
 [0,0,0],
 [7,6,5]
]
<b>Output:</b> -1

Example 3:

<b>Input:</b> 
[
 [2,3,4],
 [0,0,5],
 [8,7,6]
]
<b>Output:</b> 6
<b>Explanation:</b> You started from the point (0,0) and you can cut off the tree in (0,0) directly without walking.

Hint: size of the given matrix will not exceed 50×50.

Solution in java8 :

basically first store in increasing order of tree heights as map key with a dfs  and values as index of that tree.

Start from current location and find shortest route to next big tree with a djikstra like approach

public class Solution {

static class Pair {
int x;
int y;

// Constructor
public Pair(int x, int y)
{
this.x = x;
this.y = y;
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Pair)) return false;
Pair key = (Pair) o;
return x == key.x && y == key.y;
}

@Override
public int hashCode() {
int result = x;
result = 31 * result + y;
return result;
}
}
static class queueNode
{
Pair pt;
int dist;
}

static Map<Integer,Pair> hM = new TreeMap<>();

static boolean isSafe(Integer M[][], int row, int col,
boolean visited[][],int maxR, int maxC)
{
return (row >= 0) && (row < maxR) && (col >= 0) && (col < maxC) && (M[row][col] >= 1 && !visited[row][col]);
}

static boolean isValid(int row, int col, int ROW, int COL)
{
return (row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL);
}

static int rowNum[] = {-1, 0, 0, 1};
static int colNum[] = {0, -1, 1, 0};

//Djikstra

static int BFS(Integer mat[][], Pair src, Pair dest,int maxR,int maxC)
{

if ( mat[src.x][src.y] <1 || mat[dest.x][dest.y] <1)
return -1;
boolean visited[][] = new boolean[mat.length][mat[0].length];

visited[src.x][src.y] = true;

Queue<queueNode> q = new LinkedList<>();

queueNode qN = new queueNode();
qN.dist=0;
qN.pt=src;
q.add(qN);

while (!q.isEmpty())
{

queueNode curr = q.peek();
Pair pt = curr.pt;

if (pt.x == dest.x && pt.y == dest.y)
return curr.dist;
q.remove();

for (int i = 0; i < 4; i++)
{
int row = pt.x + rowNum[i];
int col = pt.y + colNum[i];

if (isValid(row, col,maxR,maxC) && mat[row][col]>0 &&
!visited[row][col])
{
visited[row][col] = true;
Pair AdjcellPair = new Pair(row,col);
queueNode AdjcellNode = new queueNode();
AdjcellNode.pt=AdjcellPair;
AdjcellNode.dist=curr.dist + 1;
q.add(AdjcellNode);
}
}
}

return -1;
}

static void DFS(Integer M[][], int row, int col, boolean visited[][],int maxR, int maxC)
{
int rowNbr[] = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 };
int colNbr[] = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };

if(M[row][col] >= 1) {
visited[row][col] = true;
hM.put(M[row][col],new Pair(row,col));
}

for (int k = 0; k < 8; ++k)
if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited,maxR,maxC))
DFS(M, row + rowNbr[k], col + colNbr[k], visited,maxR,maxC);
}

public static int cutOffTree(List<List<Integer>> forest) {
Integer[][] array = new Integer[forest.size()][];
int maxR=forest.size();
int maxC =forest.get(0).size();
boolean visited[][] = new boolean[forest.size()][forest.get(0).size()];

int i = 0;
for (List<Integer> nestedList : forest) {
array[i++] = nestedList.toArray(new Integer[nestedList.size()]);
}
DFS(array, 0, 0, visited,forest.size(),forest.get(0).size());
boolean flag =true;
for(int ii=0 ; ii < maxR ; ii++)
for(int j=0; j < maxC ;j++)
if(visited[ii][j]==false && array[ii][j] >0)
flag=false;

Pair curr_loc = new Pair(0,0);
int sum=0;
for(int val : hM.keySet()){
Pair p = hM.get(val);
//System.out.println(p.x + ” “+ p.y + ” ” + hM.size());
if(curr_loc.equals(p))
sum=0;
else if(BFS(array,curr_loc,p,forest.size(),forest.get(0).size())==-1)
{
sum=-1;
break;
}
else
sum+= BFS(array,curr_loc,p,forest.size(),forest.get(0).size());
curr_loc=p;
}
hM.clear();
if(sum != -1 && flag==true)
return sum;

return -1;

}

}