一、旋轉(zhuǎn)字符串

點(diǎn)我直達(dá)終點(diǎn)~

思路1

前提：如果s串和goal串長(zhǎng)度不等，則goal串不可能是s串旋轉(zhuǎn)得來(lái)，直接返回false；

通過(guò)觀(guān)察，可以發(fā)現(xiàn)每旋轉(zhuǎn)一次，第一個(gè)字符就會(huì)出現(xiàn)在最后一個(gè)字符的位置處，其余字符均往前挪動(dòng)一個(gè)位置。

所以我們首先將第一個(gè)字符保存，然后挪動(dòng)其他字符，再將保存的字符放到最后。

其次判斷s和goal是否相等，如果不等，則繼續(xù)按照上述方式旋轉(zhuǎn)

注意:如果旋轉(zhuǎn)s的長(zhǎng)度次后，與goal仍然不想等，返回false

代碼:

class Solution {
public:
    bool rotateString(string s, string goal) 
    {
    	if(s.size()!=goal.size())
    		return false;
    		
        for(int j = 0 ; j <s.size();++j)
        {
           char ch = s[0];
                //旋轉(zhuǎn)一遍
            for(int i = 1;i <s.size();++i)
            {
                s[i-1] = s[i];
            }
            s[s.size()-1] = ch;
            if(s == goal)
            {
                return true;
            }
        }

        //如果旋轉(zhuǎn)完s.size()遍，還不是true，那就false
        return false;
    }
};

時(shí)間復(fù)雜度：O(N^2) 空間復(fù)雜度：O(1)(原地旋轉(zhuǎn))

思路2

前提：如果s串和goal串長(zhǎng)度不等，則goal串不可能是s串旋轉(zhuǎn)得來(lái)，直接返回false；

一個(gè)巧妙的解法：運(yùn)用如果goal串由s串旋轉(zhuǎn)得來(lái)，那么goal串一定是s+s串的子串。
只需要判斷goal字符串是否為s+s串的子串即可。

class Solution 
{
public:
    bool rotateString(string s, string goal)
    {
        string ss = s+s;
        if(s.size() == goal.size() && ss.find(goal) != string::npos)
            return true;
        return false;
    }
};

時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度O(N)

二、親密字符串

點(diǎn)我直達(dá)終點(diǎn)~

思路

前提：如果s串和goal串長(zhǎng)度不等，則goal串不可能是s串旋轉(zhuǎn)得來(lái)，直接返回false；

對(duì)于這道題，首先遍歷一遍s串，一邊遍歷一邊與goal字符串進(jìn)行對(duì)比，如果對(duì)應(yīng)下標(biāo)的goal串的字符和s串的對(duì)應(yīng)下標(biāo)的字符不相等，則記錄不等的字符和下標(biāo)。（s串和goal串一定只有兩個(gè)不相等的字符）

找到后，如果pos1下標(biāo)和pos2下標(biāo)相同，說(shuō)明s串和goal串一定相等。
然而這里存在兩種情況，如題目描述：
情況1：ab和ab
情況2：aa和aa
此時(shí)我們不需要分情況討論，只需要找到s字符串的任意一個(gè)字符如果出現(xiàn)兩次及以上，則說(shuō)明交換s字符串的任意兩個(gè)相同的字符一定與goal字符串相等。
比如: aabab 和aabab，s字符串中的a出現(xiàn)了三次，b出現(xiàn)了兩次，
那么無(wú)論怎么交換其中的a或者b，s字符串始終和goal字符串相等。

如果字符串pos1下標(biāo)和pos2下標(biāo)不同，則交換對(duì)應(yīng)的pos1和pos2的字符，再判斷是否與goal串相等即可。

詳細(xì)請(qǐng)看代碼：

class Solution {
public:
    bool buddyStrings(string s, string goal) 
    {   
        //1.長(zhǎng)度不等，必然不是親密字符串
        if(s.size()!=goal.size())
            return false;

        char arr[2];
        //找第一個(gè)不相同的字符,并記錄下標(biāo)
        int i = 0;
        int pos1 = 0,pos2 = 0;
        for(; i<s.size();++i)
        {
            if(s[i]!=goal[i])
            {
                arr[0] = s[i];
                pos1 = i;
                break;
            }
        }

        //找第二個(gè)不相同的字符
        for(i+=1; i<s.size();++i)
        {
            if(s[i]!=goal[i])
            {
                arr[1] = s[i];
                pos2 = i;
                break;
            }
        }
        //  如果pos1 == pos2,說(shuō)明s和goal是完全相等的兩個(gè)串
        //此時(shí)有兩種情況，如果s中有兩個(gè)位置交換后還是原來(lái)的s，此時(shí)s和goal相等。
        //但不管是哪種情況，我們都只需要找出任意一個(gè)字符出現(xiàn)2次及以上就可以知道是親密字符串
        if(pos1 == pos2)
        {
            vector<int> count(26);
            for(int i = 0;i<s.size();++i)
            {
                count[s[i] - 'a']++;
                if(count[s[i] - 'a']>=2)
                    return true;
            }
            return false;
        }

        //此種情況不是s串和goal串相等，那么正常交換兩個(gè)字符的位置然后判斷是否與goal相等即可。
        else
        {
            swap(s[pos1],s[pos2]);
            if(s == goal)
                return true;

             return false;
        }
    }
};

時(shí)間復(fù)雜度：O(N)； 空間復(fù)雜度O(1) 只消耗常量個(gè)空間，即26

總結(jié)

通過(guò)這兩道題，學(xué)習(xí)到了旋轉(zhuǎn)字符串的一般規(guī)律是轉(zhuǎn)化為找子串的問(wèn)題；
而親密字符串的本質(zhì)就是分情況討論

情況1：如果s!=goal
情況2：如果s==goal

的分別處理方式。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-477625.html

到了這里，關(guān)于【每日撓頭算法題(1)】——旋轉(zhuǎn)字符串|親密字符串的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！