مراقبه های LeetCode: طراحی ساختار داده کلمات را اضافه و جستجو کنید
بیایید با توضیحات مربوط به ساختار دادههای Design Add and Search Words شروع کنیم:
یک ساختار داده طراحی کنید که از افزودن کلمات جدید و یافتن اینکه آیا یک رشته با رشته های قبلی اضافه شده مطابقت دارد یا خیر، پشتیبانی می کند.
را اجرا کنید
WordDictionary
کلاس:
WordDictionary()
شی را مقدار دهی اولیه می کند.void addWord(word)
اضافه می کندword
با ساختار داده، می توان آن را بعداً مطابقت داد.bool search(word)
برمی گرداندtrue
اگر رشته ای در ساختار داده وجود داشته باشد که مطابقت داشته باشدword
یاfalse
در غیر این صورت.word
ممکن است حاوی نقطه باشد'.'
جایی که نقطه ها را می توان با هر حرفی مطابقت داد.
مثلا:
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord('bad');
wordDictionary.addWord('dad');
wordDictionary.addWord('mad');
wordDictionary.search('pad'); // return False
wordDictionary.search('bad'); // return True
wordDictionary.search('.ad'); // return True
wordDictionary.search('b..'); // return True
ما همچنین محدودیت هایی داریم:
1 <= word.length <= 25
-
word
که درaddWord
از حروف کوچک انگلیسی تشکیل شده است. -
word
که درsearch
شامل'.'
یا حروف کوچک انگلیسی - حداکثر وجود خواهد داشت
2
نقطه درword
برایsearch
پرس و جوها - حداکثر
10^4
تماس گرفته خواهد شدaddWord
وsearch
.
از آنجایی که به خصوص با کلمات سروکار داریم ذخیره سازی و جستجوکردن در بسیاری از کلمات، ساختار داده trie می تواند برای استفاده در اینجا کارآمد باشد.
افزودن کلمات آسان است – در واقع، ما نحوه درج یک کلمه را در یک آزمایش در مشکل قبلی دیدیم.
با این حال، به نظر می رسد جستجو کمی چالش برانگیزتر باشد، زیرا ما باید کاری شبیه به جستجوی regex انجام دهیم، و از کاراکتر نقطه به عنوان علامت عام استفاده کنیم.
قبل از آن، اجازه دهید یک نفس عمیق بکشیم و با ایجاد یک گره ساده شروع کنیم.
یک گره آزمایشی ساده ممکن است به شکل زیر باشد:
class TrieNode {
public children: Map<string, TrieNode>;
public isEndOfWord: boolean;
constructor() {
this.children = new Map();
this.isEndOfWord = false;
}
}
ما TrieNode
کلاس دارد children
که یک است Map
با string
s به عنوان کلید، و TrieNode
s به عنوان مقادیر
همچنین دارای یک isEndOfWord
برای علامت گذاری گره به عنوان کاراکتر پایانی یک کلمه، پرچم گذاری کنید.
این WordDictionary
کلاس یک آزمایشی خواهد بود، بنابراین میتوانیم گره ریشه خود را در آن مقداردهی اولیه کنیم constructor
:
class WordDictionary {
public root: TrieNode;
constructor() {
this.root = new TrieNode();
}
...
}
افزودن یک کلمه دقیقاً همان کاری است که در آن انجام دادیم insert
عملکرد مشکل قبلی
ما هر شخصیت را پیمایش خواهیم کرد و یکی یکی آن را به تلاش خود اضافه می کنیم. ما یک را ایجاد خواهیم کرد currentNode
که در ابتدا به گره ریشه اشاره می کند و در حین حرکت آن را به روز می کند. در پایان، آخرین گره را به عنوان انتهای کلمه علامت گذاری می کنیم:
addWord(word: string): void {
let currentNode = this.root;
for (const char of word) {
if (!currentNode.children.has(char)) {
currentNode.children.set(char, new TrieNode());
}
currentNode = currentNode.children.get(char) as TrieNode;
}
currentNode.isEndOfWord = true;
}
توجه داشته باشید |
---|
مشابه مشکل قبلی، ما در حال کستینگ هستیم currentNode.children.get(char) به عنوان یک TrieNode ، زیرا TypeScript فکر می کند که ممکن است باشد undefined . این یکی از آن مواقعی است که ما بیشتر از کامپایلر TS می دانیم، بنابراین از یک نوع ادعا استفاده می کنیم. از طرف دیگر، میتوانیم از یک عملگر ادعای غیر تهی نیز استفاده کنیم که مقادیر را بهعنوان غیرنسخه بیان میکند. null یا undefined ، مثل این:
|
اکنون، زمانی که نیاز به پیاده سازی داریم کمی گیج کننده می شود search
. ما باید بتوانیم هر حرفی را با یک نقطه مطابقت دهیم، و ایده در اینجا درباره است چک کردن بازگشتی گره ها.
مثلاً اگر قرار باشد جستجو کنیم a.c
، ابتدا بررسی می کنیم که آیا a
وجود دارد، سپس به فرزندان آن در دو سطح زیر بروید تا ببینید آیا c
به عنوان آخرین شخصیت وجود دارد. اگر در اولین تلاش مان به هدفمان نرسیدیم، نیاز داریم عقب نشینی، و از طریق سایر فرزندان جستجو کنید a
از نو.
بنابراین، ایده این است که اگر شخصیت فعلی از word
ما به دنبال یک نقطه هستیم (.
، سپس، ما از طریق فرزندان گره فعلی و همین کار را برای هر کودک انجام دهید و با هر شخصیت در آن ادامه دهید word
.
بیایید نمونه دیگری را ببینیم.
اگر کلمه است s.y
، ابتدا بررسی می کنیم که آیا s
به عنوان یک گره فرزند ریشه وجود دارد، اگر چنین است، بررسی می کنیم که آیا گره فرزندی دارد که دارای گره فرزند باشد y
، و پایان کلمه را نشان می دهد. ما می توانیم داشته باشیم say
یا sky
یا spy
و غیره، مهم نیست. به محض اینکه با معیارهای ما مطابقت داشت، می توانیم برگردیم true
بلافاصله. مستقیما.
توجه داشته باشید که برای هر کودک، ما اساساً همان کار را انجام می دهیم، اما با شخصیت بعدی word
– این یک تابع بازگشتی است. در واقع، این یک جستجوی عمقی است.
ما شاخص فعلی شخصیتی را که در آن نگاه می کنیم، پیگیری می کنیم word
و همچنین گره فعلی.
اگر کاراکتر یک نقطه باشد (.
)، ما به بررسی هر فرزند خواهیم پرداخت و شاخص کاراکتر فعلی را افزایش می دهیم. در غیر این صورت، ما جستجوی معمول خود را انجام خواهیم داد. اگر کاراکتر در فرزندان گره فعلی نباشد، می توانیم برگردیم false
بلافاصله. مستقیما. اگر آن کاراکتر را داشته باشیم، دوباره به صورت بازگشتی جستجو می کنیم و شاخص کاراکتر را افزایش می دهیم و گره فعلی را به روز می کنیم:
function dfs(currentCharIdx: number, currentNode: TrieNode) {
if (currentCharIdx === word.length) {
return currentNode.isEndOfWord;
}
const char = word[currentCharIdx];
if (char === '.') {
for (const child of currentNode.children.values()) {
if (dfs(currentCharIdx + 1, child)) {
return true;
}
}
return false;
} else {
if (!currentNode.children.has(char)) {
return false;
}
return dfs(currentCharIdx + 1, currentNode.children.get(char) as TrieNode);
}
}
و در داخل search
، ما به سادگی می توانیم هر آنچه را که این تابع برمی گرداند، برگردانیم و اولین شاخص آن را ارسال کنیم word
و ما root
به عنوان استدلال:
return dfs(0, this.root);
در اینجا راه حل نهایی در TypeScript است:
class TrieNode {
public children: Map<string, TrieNode>;
public isEndOfWord: boolean;
constructor() {
this.children = new Map();
this.isEndOfWord = false;
}
}
class WordDictionary {
public root: TrieNode;
constructor() {
this.root = new TrieNode();
}
addWord(word: string): void {
let currentNode = this.root;
for (const char of word) {
if (!currentNode.children.has(char)) {
currentNode.children.set(char, new TrieNode());
}
currentNode = currentNode.children.get(char) as TrieNode;
}
currentNode.isEndOfWord = true;
}
search(word: string): boolean {
function dfs(currentCharIdx: number, currentNode: TrieNode) {
if (currentCharIdx === word.length) {
return currentNode.isEndOfWord;
}
const char = word[currentCharIdx];
if (char === '.') {
for (const child of currentNode.children.values()) {
if (dfs(currentCharIdx + 1, child)) {
return true;
}
}
return false;
} else {
if (!currentNode.children.has(char)) {
return false;
}
return dfs(currentCharIdx + 1, currentNode.children.get(char) as TrieNode);
}
}
return dfs(0, this.root);
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* var obj = new WordDictionary()
* obj.addWord(word)
* var param_2 = obj.search(word)
*/
پیچیدگی زمان و مکان
پیچیدگی زمانی اضافه کردن یک کلمه است
جایی که
طول کلمه است – زیرا ما از طریق هر کاراکتر یک بار تکرار می کنیم و هر بار یک عملیات ثابت را انجام می دهیم. پیچیدگی فضا نیز هست
با افزایش طول کلمه ای که اضافه می کنیم، نیاز ما به فضای اضافی افزایش می یابد.
پیچیدگی زمانی جستجو – فکر می کنم –
جایی که
طول کلمه است و
تعداد کل گره ها است. در بدترین حالت که همه کاراکترها نقطه هستند، کل درخت را برای کلمه جستجو می کنیم. پیچیدگی فضا خواهد بود
جایی که
به دلیل پشته تماس بازگشتی، ارتفاع تلاش است.
در مرحله بعد، آخرین مشکل در این فصل، جستجوی کلمه II را بررسی خواهیم کرد. تا آن زمان، کد نویسی مبارک.