首页 > 代码库 > Isomorphic Strings

Isomorphic Strings

解决这个问题的思路:将两个字符串的模式抽出来研究。以下举例说明怎样抽出一个字符串的模式。
对于paper,用1表示p。用2表示a,用3表示e,用4表示r
那么paper的模式为12134。


对于title,用1表示t,用2表示i,用3表示l。用4表示e
那么title的模式为12134。
所以同构。

编程实现中的数据结构:map

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        map<char, int> mapS1;
        int counterS1 = 0;
        for(string::iterator iter = s.begin(); iter != s.end(); iter++) {
            if(!mapS1.count(*iter)) {
                counterS1++;
                mapS1[*iter] = counterS1;
            }
        }
        vector<int> arrS1;
        for(string::iterator iter = s.begin(); iter != s.end(); iter++) {
            arrS1.push_back(mapS1[*iter]);
        }


        map<char, int> mapS2;
        int counterS2 = 0;
        for(string::iterator iter = t.begin(); iter != t.end(); iter++) {
            if(!mapS2.count(*iter)) {
                counterS2++;
                mapS2[*iter] = counterS2;
            }
        }
        vector<int> arrS2;
        for(string::iterator iter = t.begin(); iter != t.end(); iter++) {
            arrS2.push_back(mapS2[*iter]);
        }


        vector<int>::iterator iterS1, iterS2;
        iterS1 = arrS1.begin();
        iterS2 = arrS2.begin();
        for(; iterS1 != arrS1.end(); ) {
            if(*iterS1 != *iterS2)
                return false;
            iterS1++;
            iterS2++;
        }
        return true;

    }
};
<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

Isomorphic Strings