# [3304. Find the K-th Character in String Game I](https://leetcode.com/problems/find-the-k-th-character-in-string-game-i/description/)
## 1. 題目說明
- **有一個字串, 初始化為 ==`"a"`==**
- **每一步都會==擴展==該字串**
- **擴展規則：**
1. **對於字串中的所有字元，每個字元的下一個字元為擴展的字元**
2. **對於字串中的所有字元，每個擴展字元為原始字元的下一位字母**
- **ex：`"a"` => `"ab"`**
- **ex：`"ab"` => `"abbc"`**
3. **若原始字元為`"z"`，則擴展字元為`"a"`**
- **ex：`"a...z"` => `"ab...za"`**
- **使用者會輸入一整數`k`**
- **要找當 ==字串長度 > k== 時，字串中==第 k 個字元==，並輸出**
- **字串從 1 開始數**
- **ex：`"abbcbccd"`的第 5 個的字元為`'b'`**
## 2. 解題思路1 (生成字串)
- **使用==字串陣列==**
1. **每次新字串的長度都會==變長二倍==**
2. **可以創建兩個字串**
- **一個用來==生成新字串==**
- **一個用來==存入新字串==**
3. **生存新字串的方法**
- **每隔一位，插入原始字元**
- **下一位，插入生成字元**

### ● 程式碼

char kthCharacter(int k) {
    int size = 1;                              // string length
    char* temp1 = malloc(sizeof(char) * size); // 字串暫存, 用來儲存新字串
    char* temp2;       // 字串暫存, 用來生成新字串
    temp1[0] = 'a';    // 初始字串
    while (size < k) { // 直到可定址到k
        size *= 2;     // 每次長度*2
        temp2 = malloc(sizeof(char) * size); // 準備新字串空間
        for (int i = 0; i < size; i += 2) {
            temp2[i] = temp1[i / 2]; // 插入原始字串
            if (temp2[i] == 'z')     // 特殊情況插入'a'
                temp2[i + 1] = 'a';
            else // 一般情況插入下一位的字母
                temp2[i + 1] = temp2[i] + 1;
        }
        free(temp1);   // 清空戰存
        temp1 = temp2; // 存入新字串
        temp2 = NULL;  // 清空站存
    }
    return temp1[k - 1];
}

---
## 3. 解題思路2 (二元樹搜索)
- **把每次的生成結果記錄下來**
- **假設==往左子樹==的方向設為 ==`'0'`==**
- **假設==往右子樹==的方向設為 ==`'1'`==**

flowchart
    a([a]) --0--> b1([a])
    a --1--> b2([b])
    b1 --00--> c1([a]) 
    b1 --01--> c2([b])
    b2 --10--> c3([b])
    b2 --11--> c4([c])

1. **==左子節點==的==字元不變==**
2. **==右子節點==的==字元 + 1==**
3. **==第 k 個==字元的 ==index = k - 1==**
### ● 程式碼

char kthCharacter(int k) {
    int shift = 0;//初始字元'a'的位移量
    k--;//二進制表示0~k-1
    while (k > 0) {
        //右子節點為1，字母+1
        //反之不變
        shift += k % 2;
        k /= 2;
    }
    return 'a' + shift;
}