79. 尋找字串
=========================================================
難度: Medium
類型: Depth-First Search
CPP程式下載: 79.cpp
=========================================================
這個找字串, 一看就吸引了我的注意, 很像貪食蛇, 雖然難度只是中等, 但總覺得解完這題會很有成就感。
=========================================================
前情題要:
給一個 m x n 的字元矩陣, 以及一個字串。如果在 m x n 的字元陣列中能找到連續的與 word 相同的字串, 就回傳 true。 相反的, 如果找不到相同且連續的字串, 就回傳 false。
=========================================================
思考方式:
每個與 word 相同的字元, 都要去找下個字元是不是跟在上面, 下面, 左邊, 右邊的字元一致。
每個矩陣的位置只能經過一次。(跟貪食蛇一樣, 同位置去第二次會咬到自己而掛點。)
一個 m x n 的 visit_array 矩陣 (我用陣列代替) 每個初始值都為 0, 每拜訪一次 +1,下次再拜訪到就回報 false。
註: 注意邊界
=========================================================
複雜度思考:
遞迴要用的函式條列寫清楚就好。ssexist() 代表 sub string 是否還存在。
真正coding時反而覺得沒有一開始看到題目時感覺的難度那麼高。
沒有用 public global 變數, 所以傳進 ssexist 的參數有點多。
