2023-08-14：用go語言寫算法。給出兩個長度相同的字符串 str1 和 str2 請你幫忙判斷字
2023-08-14：用go語言寫算法。給出兩個長度相同的字符串 str1 和 str2，
請你幫忙判斷字符串 str1 能不能在 零次 或 多次 轉(zhuǎn)化 后變成字符串 str2，
每一次轉(zhuǎn)化時，你可以將 str1 中出現(xiàn)的 所有 相同字母變成其他 任何 小寫英文字母，
只有在字符串 str1 能夠通過上述方式順利轉(zhuǎn)化為字符串 str2 時才能返回 true 。
輸入：str1 = "aabcc", str2 = "ccdee"。
輸出：true。
來自谷歌、亞馬遜、微軟、蔚來、騰訊、字節(jié)跳動、Uber。
來自左程云。
答案2023-08-14：
大體過程如下：
1.首先，比較兩個字符串 str1 和 str2 是否相等。如果相等，則可以直接返回 true，因?yàn)椴恍枰M(jìn)行轉(zhuǎn)化操作。
2.創(chuàng)建一個長度為 26 的整數(shù)數(shù)組 mapChars，用于記錄字符串 str2 中每個字母的出現(xiàn)次數(shù)。
3.創(chuàng)建一個變量 kinds，用于記錄字符串 str2 中不同字母的種類數(shù)量。
4.遍歷字符串 str2，對于每個字符 ch，將其轉(zhuǎn)換為對應(yīng)的索引 idx。如果 mapChars[idx] 的值為 0，說明該字符還沒有出現(xiàn)過，將 kinds 值增加 1，并且將 mapChars[idx] 的值加 1。
5.如果 kinds 的值已經(jīng)達(dá)到 26（字母表中的所有字母種類數(shù)量），則說明字符串 str2 中的所有字母都已經(jīng)出現(xiàn)過，無法再進(jìn)行轉(zhuǎn)化操作，直接返回 false。
6.將 mapChars 數(shù)組中的所有元素重置為 -1。
7.遍歷字符串 str1，對于每個字符 ch，將其轉(zhuǎn)換為對應(yīng)的索引 cur。
8.如果 mapChars[cur] 不等于 -1，并且 str2[mapChars[cur]] 不等于 str2[i]，則說明已經(jīng)對字符 ch 進(jìn)行了轉(zhuǎn)化，但轉(zhuǎn)化后的字符與 str2 中對應(yīng)位置的字符不相等，直接返回 false。
9.將 mapChars[cur] 的值更新為當(dāng)前索引 i。
10.如果成功遍歷完整個字符串 str1，則說明 str1 可以通過零次或多次轉(zhuǎn)化變成字符串 str2，返回 true。
總的時間復(fù)雜度：假設(shè)字符串的長度為 n，遍歷 str2 的時間復(fù)雜度是 O(n)，遍歷 str1 的時間復(fù)雜度也是 O(n)，因此總的時間復(fù)雜度為 O(n)。
總的空間復(fù)雜度：除了字符串 str1 和 str2 的空間占用，還創(chuàng)建了長度為 26 的整數(shù)數(shù)組 mapChars，因此總的空間復(fù)雜度為 O(1)。
go語言完整代碼如下：
package?main
import?(
????"fmt"
)
func?canConvert(str1?string,?str2?string)?bool?{
????if?str1?==?str2?{
????????return?true
????}
????mapChars?:=?make([]int,?26)
????kinds?:=?0
????for?_,?ch?:=?range?str2?{
????????idx?:=?ch?-?'a'
????????if?mapChars[idx]?==?0?{
????????????kinds++
????????}
????????mapChars[idx]++
????}
????if?kinds?==?26?{
????????return?false
????}
????for?i?:=?range?mapChars?{
????????mapChars[i]?=?-1
????}
????for?i,?ch?:=?range?str1?{
????????cur?:=?ch?-?'a'
????????if?mapChars[cur]?!=?-1?&&?str2[mapChars[cur]]?!=?str2[i]?{
????????????return?false
????????}
????????mapChars[cur]?=?i
????}
????return?true
}
func?main()?{
????str1?:=?"aabcc"
????str2?:=?"ccdee"
????result?:=?canConvert(str1,?str2)
????fmt.Println(result)
}
c++完整代碼如下：
using?namespace?std;
bool?canConvert(string?str1,?string?str2)?{
????if?(str1?==?str2)?{
????????return?true;
????}
????vector<int>?map(26,?0);
????int?kinds?=?0;
????for?(int?i?=?0;?i?<?str2.length();?i++)?{
????????if?(map[str2[i]?-?'a']++?==?0)?{
????????????kinds++;
????????}
????}
????if?(kinds?==?26)?{
????????return?false;
????}
????fill(map.begin(),?map.end(),?-1);
????for?(int?i?=?0;?i?<?str1.length();?i++)?{
????????int?cur?=?str1[i]?-?'a';
????????if?(map[cur]?!=?-1?&&?str2[map[cur]]?!=?str2[i])?{
????????????return?false;
????????}
????????map[cur]?=?i;
????}
????return?true;
}
int?main()?{
????string?str1?=?"aabcc";
????string?str2?=?"ccdee";
????bool?result?=?canConvert(str1,?str2);
????cout?<<?boolalpha?<<?result?<<?endl;
????return?0;
}
c語言完整代碼如下：
bool?canConvert(const?char*?str1,?const?char*?str2)?{
????if?(strcmp(str1,?str2)?==?0)?{
????????return?true;
????}
????int?map[26]?=?{?0?};
????int?kinds?=?0;
????for?(int?i?=?0;?i?<?strlen(str2);?i++)?{
????????if?(map[str2[i]?-?'a']++?==?0)?{
????????????kinds++;
????????}
????}
????if?(kinds?==?26)?{
????????return?false;
????}
????memset(map,?-1,?sizeof(map));
????for?(int?i?=?0;?i?<?strlen(str1);?i++)?{
????????int?cur?=?str1[i]?-?'a';
????????if?(map[cur]?!=?-1?&&?str2[map[cur]]?!=?str2[i])?{
????????????return?false;
????????}
????????map[cur]?=?i;
????}
????return?true;
}
int?main()?{
????const?char*?str1?=?"aabcc";
????const?char*?str2?=?"ccdee";
????bool?result?=?canConvert(str1,?str2);
????printf("%s\n",?result???"true"?:?"false");
????return?0;
}
