【算法】交换字符 (2)

需求

给定两个字符串A和B，可以对A中的任意字符进行替换，如果要替换某个字符，则所有的此字符都要替换成相同字符。 需要判断字符串A是否可以通过字符替换得到字符串B。

例如，如果输入字符串A为“addca”，字符串B为“cookc”，则字符串A可以通过字符替换得到字符串B。 因为将A字符串中的字符'a'替换为'c'，'d'替换为'o'，'c'替换为'k'即可得到字符串B。

思路

需要判断输入的两个字符串相同位置的字符是否对应，即当A[i] == A[j]时，判断B[i] == B[j]是否成立。 算法思路如下：

1. 判断输入的两个字符串长度是否相等，如果不相等，则返回false。
2. 判断输入的两个字符串是否相等，如果相等，则返回true。
3. 对输入对第1个字符串中字符出现的位置进行统计。
4. 使用统计结果对第2个字符串进行验证，如果有位置不对应的情况出现，则返回false。

实现

package chapter05

import (
	"fmt"
	"strings"
)

func IsIsomorphic(s string, t string) bool {
	if len(s) != len(t) {
		return false
	}
	if s == t {
		return true
	}

	var dic = make(map[string][]int)
	for i, v := range s {
		k := string(v)
		dic[k] = append(dic[k], i)
	}

	fmt.Println(dic)

	// 由于第二个字符串不是通过range循环得到的，所以需要转换成[]rune，否则中文或其它特殊字符就匹配不上
	runes := []rune(t)

	for _, indexes := range dic {
		// 对应第二个字符串指定位置的字符
		w := runes[indexes[0]]

		if len(indexes) != strings.Count(t, string(w)) {
			return false
		}
		if len(indexes) > 1 {
			for _, i := range indexes {
				if w != runes[i] {
					return false
				}
			}
		}
	}

	return true
}