題目描述

題目鏈接：1417. 重新格式化字符串

給你一個混合了數(shù)字和字母的字符串 s，其中的字母均為小寫英文字母。

請你將該字符串重新格式化，使得任意兩個相鄰字符的類型都不同。也就是說，字母后面應該跟著數(shù)字，而數(shù)字后面應該跟著字母。

請你返回 重新格式化后 的字符串；如果無法按要求重新格式化，則返回一個 空字符串 。

提示:

• 1?s.length?5001 
• s 僅由小寫英文字母和/或數(shù)字組成。

示例 1：

輸入：s = "a0b1c2"
輸出："0a1b2c"
解釋："0a1b2c" 中任意兩個相鄰字符的類型都不同。 "a0b1c2", "0a1b2c", "0c2a1b" 也是滿足題目要求的答案。

示例 2：

輸入： s = "leetcode"
輸出： ""
解釋： "leetcode" 中只有字母，所以無法滿足重新格式化的條件。

示例 3：

輸入： s = "1229857369"
輸出： ""
解釋： "1229857369" 中只有數(shù)字，所以無法滿足重新格式化的條件。

示例 4：

輸入： s = "covid2019"
輸出： "c2o0v1i9d"

示例 5：

輸入： s = "ab123"
輸出： "1a2b3"

整理題意

題目給定一個字符串，僅包含小寫字母和數(shù)字，讓我們利用字符串中所給的這些字符構(gòu)造一個字符串，使得構(gòu)造出來的字符串中字母字符和數(shù)字字符不相鄰。答案返回任意一個滿足條件的字符串即可，如果無法構(gòu)造這樣的字符串返回空字符串。

解題思路分析

根據(jù)題目描述可知，為了使得字符串中不含有相鄰的字母和數(shù)字，我們盡可能的使得字母和數(shù)字交叉排列，那么當字符串中數(shù)字個數(shù)和字母個數(shù)的差值大于 1 時，無論我們怎么排列總會有兩個相同的字母字符或數(shù)字字符相鄰。

那么考慮當字符串中數(shù)字個數(shù)和字母個數(shù)的差值小于等于 1 時，我們將個數(shù)較多的種類字符放在偶數(shù)位置上，較少的字符種類放在奇數(shù)位置上（位置從 0 開始）。

具體實現(xiàn)

首先統(tǒng)計字符串中數(shù)字字符個數(shù)和字母字符個數(shù)，并判斷兩者差值是否大于 1，大于 1 的情況直接返回空字符串。

雙指針 實現(xiàn)字符串排列：

• 指針 i 指向偶數(shù)位置，j 指向奇數(shù)位置；
• 初始化 i = 0， j = 1；
• 當 i 位置上的字符不為較多的字符種類時，利用 j 指針從左到右找到第一個較多的字符種類，與位置 i 進行交換字符；
• 重復步驟 3 直至遍歷完整個字符串。

細節(jié)操作：代碼實現(xiàn)過程中僅用 if(isdigit(s[i]) != f) 這樣的判斷語句涵括了兩種情況的判斷。

復雜度分析

• 時間復雜度：O(n)，其中 n 為字符串 s 的長度，需要遍歷兩遍字符串。
• 空間復雜度：O(1)，僅使用常量空間。

代碼實現(xiàn)

class Solution {
public:
    string reformat(string s) {
        // 統(tǒng)計數(shù)字和字母的個數(shù)
        int sum_digit = 0, sum_alpha = 0;
        for(auto &c : s){
            if(isdigit(c)) sum_digit++;
            else sum_alpha++;
        }
        // 當個數(shù)差大于 1 時無法構(gòu)造
        if(abs(sum_digit - sum_alpha) > 1) return "";
        bool f = sum_digit > sum_alpha;
        int n = s.size();
        for(int i = 0, j = 1; i < n; i += 2){
            // 注意判斷語句的難點，和 f 有關(guān)
            if(isdigit(s[i]) != f){
                while(isdigit(s[j]) != f) j += 2;
                swap(s[i], s[j]);
            }
        }
        return s;
    }
};

總結(jié)

• 該題為簡單的字符串題目，需要注意的是代碼實現(xiàn)過程中的判斷語句部分，isdigit(s[i]) != f 這樣一句判斷語句即可涵括兩種情況的判斷，且判斷語句需要根據(jù) f 的定義來寫。
• 另外就是雙指針的思想，巧妙利用雙指針實現(xiàn)字符串的原地構(gòu)造。
• 測試結(jié)果：

以上就是C C++ 題解LeetCode1417重新格式化字符串的詳細內(nèi)容，更多關(guān)于C C++ 重新格式化字符串的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論