最长同构前缀-【Java实现】PTA

最长同构前缀-【Java实现】PTA

同构词是指两个词语中，相同的位置出现相同的词，"ABB"与"兴冲冲"是同构词。“abcda”与“我欺骗了我”是同构词，而"aba"与"666"不是同构词。 如果字符串s中的字符可以按某种映射关系替换得到字符串t ，那么这两个字符串是同构字符串。编写程序，对输入的两个字符串，求最长的同构前缀（前面最长有多少个是同构子串）的串长。

注意：1）每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。2）请尽量将时间复杂度控制在O(N)以内。

输入格式:

两行，每一行一个字符串，长度在1000以内，以回车表示结束。

输出格式:

输出一个整数，表示两个串构成同构词的最大前缀（前边最多有多少个字符的子串是同构的）。

输入样例1:

ABB ACDE
899 8767

输出样例1:

本输入样例中，第一个串：前四个两两相同（中间重复），后三个均不相同，第二个串前四个也两两相同（中间重复），但后三个有两个相同： 'A'->'8','B'->'9',' '->' ','C'->'7','D'->'6',但‘E’不能再对应‘7’。最长同构子串是前7个。

7

输入样例2:

*/paper_889
+-title_6667

 

输出样例2:

本输入样例中，第一个串：前四个两两相同（中间重复），后三个均不相同，第二个串前四个也两两相同（中间重复），但后三个有两个相同： 'A'->'8','B'->'9',' '->' ','C'->'7','D'->'6',但‘E’不能再对应‘7’。最长同构子串是前7个。

10

 

代码实现：

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String s1 = input.nextLine();
        String s2 = input.nextLine();
        System.out.println(isIsomorphic(s1,s2));
    }


        public static int isIsomorphic(String s, String t) {
            Map s2t = new HashMap();
            Map t2s = new HashMap();

            int len = 0;
            for (int i = 0; i < s.length(); ++i) {
                char x = s.charAt(i), y = t.charAt(i);
                if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
                    return len;
                }
                s2t.put(x, y);
                t2s.put(y, x);
                len++;
            }
            return Math.min(s.length(),t.length());
        }
}

 isIsomorphic方法也可用数组实现

public static int isIsomorphic(String s, String t) {
        char[] chars = s.toCharArray();
        char[] chart = t.toCharArray();
        int len = 0;
        int[] preIndexOfs = new int[256];
        int[] preIndexOft = new int[256];
        for (int i = 0; i < chars.length; i++) {
            if (preIndexOfs[chars[i]] != preIndexOft[chart[i]]) {
                return len;
            }
            preIndexOfs[chars[i]] = i + 1;
            preIndexOft[chart[i]] = i + 1;
            len ++;
        }
        return Math.min(s.length(),t.length());
    }