欢迎光临
我们一直在努力

【一天一道LeetCode】#205. Isomorphic Strings

一天一道LeetCode

本系列文章已全部上传至我的github,地址:ZeeCoder‘s Github
欢迎大家关注我的新浪微博,我的新浪微博
欢迎转载,转载请注明出处

(一)题目

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.

(二)解题

题目大意:给定两个字符串,s中的每个字符能个通过某种映射关系得到t,则返回true,否则返回false
解题思路:如题目给的例子,“egg”和“add”,e->a,g->d,通过这个映射关系可以得到add。
所以,很容易想到用hash表来解决这个问题。不过要注意: 不允许s中的两个不同字符对应t中的同一个字符。
即s = “ab”,t = “aa”,s中a和b不能同时对应t中的a
下面看代码:

<code><span class="hljs-keyword">class</span> Solution {
<span class="hljs-keyword">public</span>:
    <span class="hljs-keyword">bool</span> isIsomorphic(<span class="hljs-built_in">string</span> s, <span class="hljs-built_in">string</span> t) {
        <span class="hljs-keyword">int</span> len = s.length();
        <span class="hljs-keyword">if</span>(len==<span class="hljs-number">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
        <span class="hljs-comment">//必须要双向映射,避免出现一对多,多对一等情况</span>
        <span class="hljs-keyword">char</span> hash[<span class="hljs-number">256</span>];
        <span class="hljs-keyword">char</span> hash2[<span class="hljs-number">256</span>];
        <span class="hljs-built_in">memset</span>(hash,<span class="hljs-string">' '</span>,<span class="hljs-number">256</span>*<span class="hljs-keyword">sizeof</span>(<span class="hljs-keyword">char</span>));
        <span class="hljs-built_in">memset</span>(hash2,<span class="hljs-string">' '</span>,<span class="hljs-number">256</span>*<span class="hljs-keyword">sizeof</span>(<span class="hljs-keyword">char</span>));
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span> ; i &lt; len ; i++){
            <span class="hljs-keyword">if</span>(hash[s[i]]==<span class="hljs-string">' '</span>&amp;&amp;hash2[t[i]]==<span class="hljs-string">' '</span>){<span class="hljs-comment">//如果该组字符没有映射关系</span>
                hash[s[i]] = t[i];<span class="hljs-comment">//建立映射关系</span>
                hash2[t[i]] = s[i];
            }
            <span class="hljs-keyword">else</span> {
                <span class="hljs-keyword">if</span>(hash[s[i]]==t[i]&amp;&amp;hash2[t[i]]==s[i]) <span class="hljs-keyword">continue</span>;
                <span class="hljs-keyword">else</span> <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
            }
        }
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
    }
};</code>

该文章由WP-AutoPost插件自动采集发布

原文地址:http://blog.csdn.net/terence1212/article/details/51987057

未经允许不得转载:SRE空间 » 【一天一道LeetCode】#205. Isomorphic Strings

分享到:更多 ()

评论 抢沙发

评论前必须登录!

 

oracle

联系我们联系我们