[LeetCode 解題筆記] Find Smallest Letter Greater Than Target

原問題網址:744. Find Smallest Letter Greater Than Target

問題描述

給定排序過後的 character array letters ,其中只有英文小寫字母。此外,給定一個目標字母 target ,欲求 array 中大於 target 的最小元素。

另外,letters 也會 wrap around。例如: target = 'z'letters = ['a', 'b'] ,則答案為 'a'

解題思路

  1. 因為只會包含英文小寫字母,可以利用一個長度 26 的 boolean array 紀錄 letters 中哪些字母出現過(一個 linear scan 可完成)。
  2. 接著從 target 字母對應的 index 的下一格開始尋找哪一個字母在 letters  中出現過,即可找到大於 target 的最小字母為何。
  3. 不過我當初在寫這題的時候沒注意到題目有提到「已排序」這個條件,這個解法只能達到 linear time。可見官方解答有更快的解法

以下為用 C 語言實作的程式碼:

char nextGreatestLetter(char* letters, int lettersSize, char target){
  bool has_character[26];
  for (int i = 0; i < 26; i++) {
    has_character[i] = false;
  }
  for (int i = 0; i < lettersSize; i++) {
    has_character[letters[i] - 'a'] = true;
  }
  int next_greatest_letter_index = (target - 'a' + 1) % 26;
  while (!has_character[next_greatest_letter_index]) {
      next_greatest_letter_index = (next_greatest_letter_index + 1) % 26;
  }
  return 'a' + next_greatest_letter_index;
}

Show Comments