algorithm - Interview Prep Words in a Grid -


i've been doing interview prep questions , question i've had trouble i'm unsure how implement solution. here's setup. you're given 8x8 grid of letters , list of words, , must return longest word in list can formed starting @ letter on grid , moving grid in way knight in chess. example, if had list ["word", "string", "test"] , following grid:

y w e z t n u w o p a c q g f t e l z x c v b n m m w f r t o u o n s d f b e j o l z v c t b n m q w e r t s g x z r s

then return "test", because can formed starting @ bottom left corner of grid 't', jumping 2 , right 1 'e', jumping down 2 , right 1 's', , left 2 , 1 't', , none of other words can formed on grid.

i think you'd use branch , bound algorithm i'm totally lost on how set up. help? i'm trying implement in python.

note: letters can repeated in grid, i.e. can jump on same letter many times want.

my solution is: every word in array, iterate through matrix find first letter can use breath first search (bfs) or depth first search (dfs) on first letter's neighbors( in case 8 positions knight can jump to) see if match up. can implement bfs or dfs iteratively using queue or stack respectively.


-

Comments

Post a Comment

Popular posts from this blog

unity3d - Rotate an object to face an opposite direction -

i have object , b. when click on object b, rotates object b (a faces b). b doesn't face a. need following : when faces b, need face opposite direction. have code rotating @ b. how rotate face opposite direction after that? vector3 targetdirection = target - transform.position; float step = speed * time.deltatime; vector3 newdirection = vector3.rotatetowards (turretdome.transform.forward, targetdirection, step, 0.0f); turretdome.transform.rotation = quaternion.lookrotation (newdirection); you object facing object b, want inverse direction of object after that? objecta.transform.rotation = quaternion.inverse(objecta.transform.rotation) but lets assume example turretdome object a, (negate direction): turretdome.transform.rotation = quaternion.lookrotation (-newdirection); naturally, both of these snippets not show how smoothen rotation, seem know how use time.deltatime. just incase unsure, quaternion.lerp this
Read more

angular - Is it possible to get native element for formControl? -

i've got angular2 reactive form . created formcontrol s , assigned input fields by [formcontrol]=... . understand creates nativeelement <-> formcontrol link. my question: possible nativeelement formcontrol ? wanna myformcontrol.nativeelement.focus() i can share 1 terrible solution works me. in reactive forms can use either 1) formcontroldirective ts mycontrol = new formcontrol('') template <input type="text" [formcontrol]="mycontrol"> or 2) formcontrolname ts myform: formgroup; constructor(private fb: formbuilder) {} ngoninit() { this.myform = this.fb.group({ foo: '' }); } template <form [formgroup]="myform"> <input type="text" formcontrolname="foo"> </form> so these directives write patch like 1) formcontroldirective const originformcontrolngonchanges = formcontroldirective.prototype.ngonchanges; formcontroldirective.proto
Read more

javascript - Why jQuery Select box change event is now working? -

i working on product filters user select select box according his/her preference not getting selected value user in jquery. html code:- <select name="product_filter" id="product_filter"> <option value="price_low_first">price : low high</option> <option value="price_high_first">price : high low</option> <option value="latest">latest</option> <option value="popular">most popular</option> </select> jquery code: $(function () { $("#product_filter").change(function () { alert("hi") var selectedtext = $(this).find("option:selected").text(); var selectedvalue = $(this).val(); alert("selected text: " + selectedtext + " value: " + selectedvalue); }); }); hi believe code perfect. once please check jquery.min.js
Read more