[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;
}