# LeetCode 3146. Permutation Difference between Two Strings

###### tags: `python`,`LeetCode`
>這邊使用Python解題
>時間複雜度為 O(n^2)
>另外附上我與老大哥討論出來更好的做法，在下方更新處，時間複雜度為O(n)

## 題目：
You are given two strings `s` and `t` such that every character occurs at most once in `s` and `t` is a permutation of `s`.

The **permutation difference** between `s` and `t` is defined as the **sum** of the absolute difference between the index of the occurrence of each character in `s` and the index of the occurrence of the same character in `t`.

Return the **permutation difference** between `s` and `t`.

白話文: `s`是給定的字串，`t`是不同排列組合的`s`，答案需要回傳在`s`中出現的索引與相同字元在`t`中出現的索引之間的絕對差之和。

## 範例
### 範例 1:

Input: s = "abc", t = "bac"
Output: 2

Explanation:

For s = "abc" and t = "bac", the permutation difference of s and t is equal to the sum of:

The absolute difference between the index of the occurrence of "a" in s and the index of the occurrence of "a" in t.
The absolute difference between the index of the occurrence of "b" in s and the index of the occurrence of "b" in t.
The absolute difference between the index of the occurrence of "c" in s and the index of the occurrence of "c" in t.
That is, the permutation difference between s and t is equal to |0 - 1| + |2 - 2| + |1 - 0| = 2.

### 範例 2:

Input: s = "abcde", t = "edbac"
Output: 12

Explanation: The permutation difference between s and t is equal to |0 - 3| + |1 - 2| + |2 - 4| + |3 - 1| + |4 - 0| = 12.

## 條件限制
* `1 <= s.length <= 26`
* Each character occurs at most once in `s`.
* `t` is a permutation of `s`.
* `s` consists only of lowercase English letters.

## 我的解題思路：
這題需要走訪`s`字串中的所有元素，並找到該元素對應在`t`字串元素的索引位置，將`s`的索引減去`t`的索引後取絕對值做加總。

神奇的表達方法:
`|s[0] - t[s[0]]| + |s[1] - t[s[1]]| + ... |s[n-1] - t[s[n-1]]|`

## 程式碼:

def findPermutationDifference(self, s: str, t: str) -> int:
    ans = 0
    for item in s:
        ans = ans + abs(s.index(item) - t.index(item))

    return ans

## 更新後更好的做法:

def findPermutationDifference(self, s: str, t: str) -> int:
    data_map = {}
    for i in range(len(t)):
        data_map[t[i]] = i

    ans = 0

    for i in range(len(s)):
        ans += abs(i - data_map[s[i]])
    return ans

解釋:
`t`&`s`都是字串，index就都是O(n)，所以改個方式使用一個長度為26的陣列(假設是`a`)存`s`每個字元的index，像這樣`a[s[i]-‘a’] =i`，再用另一個迴圈走訪`t`，`sum+=abs(i-s[t[i]-‘a’])`，`sum`就會是答案了，這樣會是2n =O(n)。

###### Topic: `String` `Hash Table`