0079-word-search.rs

#[inline(always)]
pubfnencode(c:char) -> u8{
 c asu8 - b'A' + 1
}

#[inline]
pubfnencode_word(mutword:String,counter:&mut[i8]) -> u128{
letmut res :u128 = 0;
let end_char = encode(word.chars().next_back().unwrap())asusize;
let start_char = encode(word.chars().next().unwrap())asusize;

if counter[end_char] > counter[start_char]{
whileletSome(c) = word.pop(){
 res <<= 6;
let byte = encode(c);
 counter[byte asusize] -= 1;
 res |= byte asu128;
}
}else{
for c in word.chars(){
 res <<= 6;
let byte = encode(c);
 counter[byte asusize] -= 1;
 res |= byte asu128;
}
}

 res
}

implSolution{
pubfnexist(board:Vec<Vec<char>>,word:String) -> bool{
if board.len()* board[0].len() < word.len(){
returnfalse;
}

letmut counter :[i8;60] = [0;60];
let board :Vec<Vec<u8>> = board
.into_iter()
.map(|row| 
 row.into_iter().map(|ele| {
letmut res = encode(ele);
 counter[res asusize] += 1;
 res
})
.collect()
).collect();

let word = encode_word(word,&mut counter);

if counter.into_iter().any(|&count| count < 0){
returnfalse;
}

letmut visited :Vec<Vec<bool>> = vec![vec![false; board[0].len()]; board.len()];

for i in0..board.len(){
for j in0..board[0].len(){
ifSelf::backtrack(word,&board, i, j,&mut visited){
returntrue;
}
}
}

false
}

#[inline(always)]
pubfnbacktrack(
mutword:u128,
board:&[Vec<u8>],
i:usize,j:usize,
visited:&mut[Vec<bool>]
) -> bool{
if i >= board.len() || j >= board[i].len() || word asu8&0b111111 != board[i][j] || visited[i][j]{
returnfalse;
}

 visited[i][j] = true;

({ word >>= 6; word == 0})
 ||(Self::backtrack(word, board, i + 1, j, visited))
 ||(Self::backtrack(word, board, i, j + 1, visited))
 ||(Self::backtrack(word, board, i - 1, j, visited))
 ||(Self::backtrack(word, board, i, j - 1, visited))
 ||({
 visited[i][j] = false;
false
})

}
}