java字符串练习题8、同构字符串

红目香薰

发布于 2023-01-13 10:12:27

1390

发布于 2023-01-13 10:12:27

文章被收录于专栏：CSDNToQQCode

java字符串练习题8、同构字符串

题目：

给定两个字符串 s 和 t ，判断它们是否是同构的。如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

测试数据：

示例 1:

输入：s = "egg", t = "add" 输出：true

示例 2：

输入：s = "foo", t = "bar" 输出：false

示例 3：

输入：s = "paper", t = "title" 输出：true

提示：

1 <= s.length <= 50000

t.length == s.length

s 和 t 由任意有效的 ASCII 字符组成

题解：

同构字符串也就是相同的结构呗，那么咱们在理解的过程中就例如【abbc】对照【deef】

我用数组解的，相对相率应该是高于链表的，很多题目都是这样，用数组有的时候更合适。

这里要两个变量，题目中也说了【s 和 t 由任意有效的 ASCII 字符组成】，那么我们创造数组的时候长度给127就行，大了没用。

这个题目就是纯数组的理论，还有字符串以及字符的处理，当我们基础知识很夯实的时候就会很容易想出来各种各样的解决方法，所以刷题很重要。

package com.item.actoin;

import java.util.Scanner;

public class Demo {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String t = sc.next();
		sc.close();
		boolean result = true;
		//都转成字符数组·t.length == s.length
		char[] chars = s.toCharArray();
		char[] chart = t.toCharArray();
		//反正都是ASCII，不可能有效的超过byte
		int[] preIndexOfs = new int[127];
		int[] preIndexOft = new int[127];
		//遍历的时候注意判断格式就行
		for (int i = 0; i < chars.length; i++) {
			System.out.println(preIndexOfs[chars[i]]+","+chars[i]+"對比"+preIndexOft[chart[i]]+","+chars[i]);
			//只要相同就能继续累加·只要有任何一个格式不一样就结束循环
			if (preIndexOfs[chars[i]] != preIndexOft[chart[i]]) {
				result = false;
				break;
			}
			// 只要是一样咱们就变一下·用作记录
			preIndexOfs[chars[i]] = 1;
			preIndexOft[chart[i]] = 1;
		}
		System.out.println(result);
	}
}

输出效果：

还有很多其它的解法，使用哈希表来处理。但是这种效率会低一些。

提交源码：

package com.item.actoin;

import java.util.Scanner;

public class Demo {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String t = sc.next();
		sc.close();
		boolean result = true;
		//都转成字符数组·t.length == s.length
		char[] chars = s.toCharArray();
		char[] chart = t.toCharArray();
		//反正都是ASCII，不可能有效的超过byte
		int[] preIndexOfs = new int[127];
		int[] preIndexOft = new int[127];
		//遍历的时候注意判断格式就行
		for (int i = 0; i < chars.length; i++) {
			//只要相同就能继续累加·只要有任何一个格式不一样就结束循环
			if (preIndexOfs[chars[i]] != preIndexOft[chart[i]]) {
				result = false;
				break;
			}
			// 只要是一样咱们就变一下·用作记录
			preIndexOfs[chars[i]] = 1;
			preIndexOft[chart[i]] = 1;
		}
		System.out.println(result);
	}
}