网站商城建设,电商网站开发,网上商城有哪些,平台推广方案205. Isomorphic Strings(同构字符串)
对于同构字符串来说也就是对于字符串s与字符串t#xff0c;对于 s [ i ] s[i] s[i]可以映射到 t [ i ] t[i] t[i],同时对于任意 s [ k ] s [ i ] s[k]s[i] s[k]s[i]都有 s [ k ] s[k] s[k]映射到 t [ k ] t[k] t[k],则 t [ k ] t [ i …205. Isomorphic Strings(同构字符串)
对于同构字符串来说也就是对于字符串s与字符串t对于 s [ i ] s[i] s[i]可以映射到 t [ i ] t[i] t[i],同时对于任意 s [ k ] s [ i ] s[k]s[i] s[k]s[i]都有 s [ k ] s[k] s[k]映射到 t [ k ] t[k] t[k],则 t [ k ] t [ i ] t[k]t[i] t[k]t[i]则说明这是一个同构字符串。 我们已经明白了映射规则接下来我们就具体来分析下如何判断是否为同构字符串。 在ASCII码对照表中一共有128个字符也就是说对于题目给出的字符串我们可以确定它们是这128个字符中的字符组成的每个字符都有两种表示一种是ASCII码一种是字符本身。 我们就可以创建一个大小为128的char类型数组f用ASCII码 x x x作为下标表示s中所有ASCII码为 x x x的元素 f [ x ] f[x] f[x]映射为t中的对应位置的元素。 映射如图所示 之后每一次添加映射都要对应的映射f[s[i]]是否已经存在如果存在是否与当前要添加的映射是否相同如果相同则没事不相同就说明存在一个映射到多个元素那就不符合同构字符串的定义了。 之后我们还需要检查一下是否存在多个元素映射到同一个元素的情况存在因为上述添加的过程在建立映射后只能保证不存在一个映射到多个的情形但是没法避免多个元素到一个元素的情形所以我们需要进行额外的检查。
总结
根据字符的两种表现形式我们可以建立数组描述映射。我们可以发现在遍历字符串s与t将对应位置的元素映射关系逐一加入到f数组中在加入的过程中如果发现映射已存在但是映射的元素不相同说明这两个不是同构字符串我们返回false一直到结束如果s中所有元素都与t中对应位置的元素建立了映射则我们需要检查是否存在多个s中的不同字符映射到了t中的同一个字符上如果存在返回false否则返回true。 至此程序结束。
bool isIsomorphic(char* s, char* t) {int length1 strlen(s);int length2 strlen(t);char * f (char *)malloc(sizeof(char)*128);for(int i 0; i 128; i){f[i] 0;}if(length1length2){for(int i 0; i length1; i){if(f[s[i]]0){f[s[i]] t[i];}else if(f[s[i]]!t[i]){return 0;}}for(int i 0; i 128; i){for(int j 0; j i; j){if(f[i]f[j]f[i]!0){return 0;}}}return 1;}return 0;
}运行结果截图
