当前位置:首页 > 高性能开发 > 数据结构与算法

数据结构与算法温习-leetcodeOJ题解

优良自学吧提供数据结构与算法温习-leetcodeOJ题解,数据结构与算法复习-----leetcodeOJ题解Isomorphic Strings      Given two strings s and t, determin

数据结构与算法复习-----leetcodeOJ题解

Isomorphic Strings

     Given two strings s and t, determine if they are isomorphic.

     Two strings are isomorphic if the characters in s can be replaced to get t.

      All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

 (一个字符与另一个字符的替换一定是按照字符的顺序发生的。两个不同的字符不能同时映射到同一个字符,但是一个字符可以映射到它自己。)

      For example,
      Given "egg", "add", return true.

       Given "foo", "bar", return false.

     Given "paper", "title", return true.

    Note:
    You may assume both s and t have the same length.

说明:LeetCode OJ is a platform for preparing technical coding interviews. Pick from an expanding library of more than 190 questions, code and submit your solution to see if you have solved it correctly. It is that easy!

题目分析:判断两个字符串是否同构。

  解题思路:使用两个hashmap,map和map1一个放置s到t的映射,另一个放置t到s的映射,循环遍历两个字符串的每个字符,key和value分别等于s和t的第i个字符,如果map中已经存在当前的key,则需要判断value是否与map中取出的值是否相等,如果不相等直接return false;

这样就确保了s到t同一个字符不会映射到不同的字符上。同理,map1存放t到s的映射,确保t到s同一个字符不会映射到不同的字符上.

 

代码:

 1 public class Solution {
 2     public static boolean isIsomorphic(String s, String t) {
 3             
 4             if(null==s&&null==t){
 5                
 6                 return true;
 7             }
 8             if(s.length()!=t.length()){
 9                
10                 return false;
11             }
12             //循环遍历两个字符串的每个字符,把s的每个字符当做键,t中的每个字符当做值,
13             //每次放入map之前,检查是否存在键,若存在,检查值是否相等,若相等,继续,若不等,返回false
14             Map<Character,Character> map=new HashMap<Character,Character>();
15             Map<Character,Character> map1=new HashMap<Character,Character>();
16             char key;
17             char value;
18             for(int i=0;i<s.length();i++){
19                 key=s.charAt(i);
20                 value=t.charAt(i);
21                
22                 if(map.containsKey((Character)key)){
23                     if(value!=map.get((Character)key)){
24                         return false;
25                     }
26                 }else{
27                     if(map1.containsKey(value)){
28                          if(key!=map1.get((Character)value)){
29                              return false;
30                          }
31                     }
32                     map.put(key,value);
33                     map1.put(value, key);
34                 }
35             }
36             return true;
37         }
38 }

 


(本文来自互联网,不代表搜站(http://www.ylzx8.cn/)的观点和立场)
本站所有内容来自互联网,若本站收录的信息无意侵犯了贵司版权,请给我们来信(ylzx8cn@163.com),我们会及时处理和回复,谢谢