مراقبه های 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 با strings به عنوان کلید، و TrieNodes به عنوان مقادیر

همچنین دارای یک 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;
}

اکنون، زمانی که نیاز به پیاده سازی داریم کمی گیج کننده می شود 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)
 */

پیچیدگی زمان و مکان

پیچیدگی زمانی اضافه کردن یک کلمه است

$بر)$

جایی که

$n$

طول کلمه است – زیرا ما از طریق هر کاراکتر یک بار تکرار می کنیم و هر بار یک عملیات ثابت را انجام می دهیم. پیچیدگی فضا نیز هست

$بر)$

با افزایش طول کلمه ای که اضافه می کنیم، نیاز ما به فضای اضافی افزایش می یابد.

پیچیدگی زمانی جستجو – فکر می کنم –

$O(n * m)$

جایی که

$n$

طول کلمه است و

$متر$

تعداد کل گره ها است. در بدترین حالت که همه کاراکترها نقطه هستند، کل درخت را برای کلمه جستجو می کنیم. پیچیدگی فضا خواهد بود

$O(h)$

جایی که

$ساعت$

به دلیل پشته تماس بازگشتی، ارتفاع تلاش است.

در مرحله بعد، آخرین مشکل در این فصل، جستجوی کلمه II را بررسی خواهیم کرد. تا آن زمان، کد نویسی مبارک.