package Ġle et code Ċ Ċ /** Ċ 7 9 . Ġ åįķ è¯į æĲľç´¢ Ċ https :// leetcode - cn . com / problems / word - search / Ċ ç»Ļ å®ļ ä¸Ģä¸ª äºĮ ç»´ ç½ĳ æł¼ åĴĮ ä¸Ģä¸ª åįķ è¯į ï¼Į æī¾ åĩº è¯¥ åįķ è¯į æĺ¯åĲ¦ åŃĺåľ¨ äºİ ç½ĳ æł¼ ä¸Ń ãĢĤ Ċ Ċ åįķ è¯į å¿ħé¡» æĮīçħ§ åŃĹ æ¯į é¡ºåºı ï¼Į éĢļè¿ĩ çĽ¸ éĤ » çļĦ åįķåħĥ æł¼ åĨħ çļĦ åŃĹ æ¯į æŀĦ æĪĲ ï¼Į åħ¶ä¸Ń âĢľ çĽ¸ éĤ » âĢĿ åįķåħĥ æł¼ æĺ¯ éĤ£ äºĽ æ°´ å¹³ çĽ¸ éĤ » æĪĸ åŀ Ĥ çĽ´ çĽ¸ éĤ » çļĦ åįķåħĥ æł¼ ãĢĤ åĲĮ ä¸Ģä¸ª åįķåħĥ æł¼ åĨħ çļĦ åŃĹ æ¯į ä¸į åħģè®¸ è¢« éĩįå¤į ä½¿çĶ¨ ãĢĤ Ċ Ċ ç¤ºä¾ĭ : Ċ Ċ board Ġ= Ċ [ Ċ [' A ',' B ',' C ',' E '], Ċ [' S ',' F ',' C ',' S '], Ċ [' A ',' D ',' E ',' E '] Ċ ] Ċ Ċ ç»Ļ å®ļ Ġword Ġ= Ġ" AB CC ED ", Ġè¿ĶåĽŀ Ġtrue . Ċ ç»Ļ å®ļ Ġword Ġ= Ġ" SE E ", Ġè¿ĶåĽŀ Ġtrue . Ċ ç»Ļ å®ļ Ġword Ġ= Ġ" AB CB ", Ġè¿ĶåĽŀ Ġfalse . Ċ Ċ æĿ¥ æºĲ ï¼ļ åĬĽ æī £ ï¼Ī LeetCode ï¼ī Ċ éĵ¾æİ¥ ï¼ļ https :// leetcode - cn . com / problems / word - search Ċ èĳĹ ä½ľ æĿĥ å½Ĵ é¢Ĩ æī £ ç½ĳç»ľ æīĢæľī ãĢĤ åķĨ ä¸ļ è½¬ è½½ è¯· èģĶç³» å®ĺæĸ¹ æİĪæĿĥ ï¼Į éĿŀ åķĨ ä¸ļ è½¬ è½½ è¯· æ³¨ æĺİ åĩº å¤Ħ ãĢĤ ĊĠĠĠĠĠĠĠ Ġ**/ Ċ Ċ object ĠWord Search Ġ{ ĊĠĠĠ Ġclass ĠSolution Ġ{ ĊĊĠĠĠĠĠĠĠ Ġvar Ġans Ġ= Ġfalse ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* Ġ åĽŀ æº ¯ æ³ķ ï¼ļ ĊĠĠĠĠĠĠĠĠ Ġ* Ġres = Ġ[] ĊĠĠĠĠĠĠĠĠ Ġ* Ġback Track ( è·¯å¾Ħ ï¼Į éĢīæĭ© éĽĨ ) Ġ{ ĊĠĠĠĠĠĠĠĠ Ġ* Ġ Ġif Ġ( ç»ĵæĿŁ æĿ¡ä»¶ ï¼ī { ĊĠĠĠĠĠĠĠĠ Ġ* Ġ Ġres . add ( è·¯å¾Ħ ) ĊĠĠĠĠĠĠĠĠ Ġ* Ġ Ġ} ĊĠĠĠĠĠĠĠĠ Ġ* Ġ Ġfor Ġ( éĢīæĭ© Ġin Ġ éĢīæĭ© éĽĨ ) Ġ{ ĊĠĠĠĠĠĠĠĠ Ġ* ĠĠĠĠĠ Ġ éĢīæĭ© ĊĠĠĠĠĠĠĠĠ Ġ* ĠĠĠĠĠ Ġback Track ( è·¯å¾Ħ ï¼Į éĢīæĭ© éĽĨ ) ĊĠĠĠĠĠĠĠĠ Ġ* ĠĠĠĠĠ Ġæ Ĵ ¤ éĶĢ éĢīæĭ© ĊĠĠĠĠĠĠĠĠ Ġ* Ġ Ġ} https :// leetcode - cn . com / problems / word - search / solution / java - sh en - du - s ou - su o - h ui - su - by - deep 2 0 1 8 5 3 0 / ĊĠĠĠĠĠĠĠĠ Ġ* Ġ} ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġexist ( board : ĠArray < CharArray >, Ġword : ĠString ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġboard . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġ 0 Ġuntil Ġboard [ i ]. size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif ( back Track ( board , word , i , j , 0 )){ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġrows Ġ= Ġint ArrayOf ( 0 , 1 , 0 ,- 1 ) ĊĠĠĠĠĠĠĠ Ġval Ġcols Ġ= Ġint ArrayOf ( 1 , 0 ,- 1 , 0 ) ĊĊĠĠĠĠĠĠĠ Ġfun Ġback Track ( board : ĠArray < CharArray >, word : String , x : ĠInt , y : ĠInt , start : ĠInt ): Boolean Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠåĪ¤æĸŃ è¶Ĭ çķĮ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif ( x Ġ>= Ġboard . size Ġ|| Ġx Ġ< Ġ 0 Ġ|| Ġy Ġ>= Ġboard [ 0 ]. size Ġ|| Ġy Ġ< Ġ 0 ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( board [ x ][ y ] Ġ!= Ġword [ start ]) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( word . length Ġ- Ġ 1 Ġ== Ġstart Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġboard [ x ][ y ] Ġ= Ġ'.' ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġ 4 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( back Track ( board , word , x Ġ+ Ġrows [ i ], Ġy Ġ+ Ġcols [ i ], start Ġ+ Ġ 1 )){ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġboard [ x ][ y ] Ġ= Ġword [ start ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ }