---
# System prepended metadata

title: "3412.\_Find\_Mirror\_Score\_of\_a\_String"
tags: [LeetCode]

---

# [3412. Find Mirror Score of a String](https://leetcode.com/problems/find-mirror-score-of-a-string/description/)

## 1. 題目說明
- **你會得到一個字串 `s`**
- **若有兩個字母 ==`字母1`==、==`字母2`==**
    - **假設 ==`字母'a'`== 與 `字母1` 的間距為 ==`index1`==**
    - **假設 ==`字母'z'`== 與 `字母2` 的間距為 ==`index2`==**
    - **若 ==`index1 = index2`==，定義該關係為==鏡像==**
    - **ex：==`a` 鏡像 `z`==、==`b` 鏡像 `y`==、==`c` 鏡像 `x`==**
- **我們需要利用鏡像的規則計算分數**
    1. **已知 ==字串`s`== 中的某個字元的索引為 ==`index1`==**
    2. **若該字元在==字串`s`== 中有最靠近 ==鏡像字母==，且鏡像字母的索引為 ==`index2`==**
    3. **則得分為 ==`|index2 - index1|`==**
    4. **已==配對過鏡像關係==的字母==不能再次配對==鏡像關係**
- **在==字串`s`== 中找出所有的鏡像字母，並==加總所有得分==**
- **回傳總分**
## 2. 解題思路1
- **需要記錄所有字母的==索引==，適合 ==`hash`==**
- **相同的字母可能會出現多次，會有==不同的索引==**
    - **且==配對過==的字母索引會==捨棄==，考慮 ==`queue`==、==`stack`==**
    - **優先捨棄==最靠近的索引(最後輸入的索引)==，符合==LIFO==，使用 ==`stack`==**
1. **先做一個 ==`hash`== 為一個存放 26 個字母索引 ==`26 * 1` 的 Stack==**
2. **遍歷 ==字串`s`== 的所有字元**
    - **若遍歷的字元對應的鏡像字母==存在索引==**
        1. **==分數 + 當前字母的索引==**
        2. **==`pop`== 鏡像字母的索引**
        2. **==分數 - `pop` 的值==**
    - **若==不存在索引==**
        1. **==`push` 當前字母的索引== 至 ==當前字母的 stack==**

### ● 程式碼
```cpp=
//實作Linked List Stack
struct node {
    int data;
    struct node* next; // next 指向前一個node
};
struct stack {
    struct node* top; // stack 存儲 top node
};
struct stack* createStack() {
    struct stack* obj = malloc(sizeof(struct stack));
    obj->top = NULL;
    return obj;
}
void push(struct stack* obj, int data) {
    // 創建一個新的 top node，指向原本的 top node
    struct node* p = malloc(sizeof(struct node));
    p->data = data;
    p->next = obj->top;
    obj->top = p;
}
struct node* pop(struct stack* obj) {
    if (!obj || !obj->top)
        return NULL;
    //把 top 設為下一個 node
    //return 原本 top 中的資料
    struct node* reg = obj->top;
    obj->top = reg->next;
    /*int* data = malloc(sizeof(int));
    *data = reg->data;
    free(reg);*/
    return reg;
}
//hash 的實作方法
struct stack** createHash() {
    //創建一個 26個 的 Linked List Stack
    struct stack **obj = malloc(sizeof(struct stack*)*26);
    //初始化 26個 Stack
    for (int i = 0; i < 26; i++)
        obj[i] = createStack();

    return obj;
}
long long calculateScore(char* s) {
    long long score = 0;
    struct stack** hash = createHash();
    //遍歷所有字符
    for (int i = 0; s[i]; i++) {
        //若有找到鏡像字母，計算分數
        if (hash['z' - s[i]]->top){
            score += i;
            struct node *reg = pop(hash['z' - s[i]]);
            score -= reg->data;
            free(reg);
        } 
        // 若沒有，存入 index 至對應字母的 Stack
        else {
            push(hash[s[i] - 'a'], i);
        }
    }
    return score;
}
```
---