ধরুন একটি ২ডি বোর্ড এবং শব্দের একটি তালিকা আছে। ডিকশনারি থেকে বোর্ডে পাওয়া সব শব্দ খুঁজে বের করতে হবে। প্রতিটি শব্দ আশেপাশের সেলের অক্ষর থেকে ক্রমাগত গঠন করতে হবে (ক্ষতিজ বা উল্লম্ব)। একই লেটার সেল একটি শব্দে একবার বেশি ব্যবহার করা যাবে না।
সমাধানের ধাপগুলো −
- result অ্যারে তৈরি করুন
- solve() মেথড সংজ্ঞায়িত করুন যা board, d, i, j, s নেবে
- যদি i বা j বোর্ডের রেঞ্জের বাইরে হয় তবে false রিটার্ন করুন
- l := board[i][j]
- যদি l d-তে থাকে তবে d := d[l], s += l
- যদি '#' d-তে থাকে এবং d['#'] null না হয় তবে s result-এ যোগ করুন, d['#'] := 0
- board[i][j] := '*' (ভিজিটেড মার্ক করুন)
- চার দিকের জন্য রিকার্সিভ কল করুন যদি সেল d-তে থাকে
- board[i][j] := l (ব্যাকট্র্যাক)
- insert() মেথড সংজ্ঞায়িত করুন word এবং dictionary t নিয়ে
- current := t; word-এর প্রতিটি ক্যারেক্টার জন্য current[i] = {} তৈরি করুন; current['#'] = 1
- মূল মেথড থেকে − t = {}; প্রতিটি word-এর জন্য insert(word, t); বোর্ডের প্রতিটি সেলের জন্য solve(board, t, i, j) কল করুন; result রিটার্ন করুন
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন −
class Solution(object):
def findWords(self, board, words):
self.result = []
t = {}
for word in words:
self.insert(word,t)
for i in range(len(board)):
for j in range(len(board[0])):
self.solve(board,t,i,j)
return self.result
def solve(self,board,d,i,j,s=""):
if i<0 or j<0 or i>=len(board) or j>=(len(board[0])):
return
l = board[i][j]
if l in d:
d = d[l]
s+=l
if "#" in d and d['#']:
self.result.append(s)
d['#'] = 0
board[i][j] = '*'
if i+1=0 and board[i-1][j] in d:
self.solve(board,d,i-1,j,s)
if j-1>=0 and board[i][j-1] in d:
self.solve(board,d,i,j-1,s)
board[i][j] = l
def insert(self, word,t):
current = t
for i in word:
if i not in current:
current[i] = {}
current =current[i]
current['#']=1
ob = Solution()
print(ob.findWords([["o","a","a","n"],["e","t","e","a"],["i","h","k", "r"],["i","f","l","v"]],["oath","pea","tea","rain"]))
ইনপুট
[["o","a","a","n"], ["e","t","e","a"], ["i","h","k","r"], ["i","f","l","v"]], ["oath","pea","tea","rain"]
আউটপুট
['oath', 'tea']
