interleaving Archives - Huahua's Tech Road

Given alphanumeric string s. (Alphanumeric string is a string consisting of lowercase English letters and digits).

You have to find a permutation of the string where no letter is followed by another letter and no digit is followed by another digit. That is, no two adjacent characters have the same type.

Return the reformatted string or return an empty string if it is impossible to reformat the string.

Example 1:

Input: s = "a0b1c2"
Output: "0a1b2c"
Explanation: No two adjacent characters have the same type in "0a1b2c". "a0b1c2", "0a1b2c", "0c2a1b" are also valid permutations.

Example 2:

Input: s = "leetcode"
Output: ""
Explanation: "leetcode" has only characters so we cannot separate them by digits.

Example 3:

Input: s = "1229857369"
Output: ""
Explanation: "1229857369" has only digits so we cannot separate them by characters.

Example 4:

Input: s = "covid2019"
Output: "c2o0v1i9d"

Example 5:

Input: s = "ab123"
Output: "1a2b3"

Constraints:

1 <= s.length <= 500
s consists of only lowercase English letters and/or digits.

Solution: Two streams

Create two stacks, one for alphas, another for numbers. If the larger stack has more than one element than the other one then no solution, return “”. Otherwise, interleave two stacks, start with the larger one.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

string reformat(string s) {

string q1;

string q2;

for (char c : s) {

if (isalpha(c))

q1 += c;

else

q2 += c;

}

if (q1.length() < q2.length())

swap(q1, q2);

if (q1.length() > q2.length() + 1)

return "";

string ans;

while (!q1.empty()) {

ans += q1.back();

q1.pop_back();

if (q2.empty()) break;

ans += q2.back();

q2.pop_back();

}

return ans;

}

};

Solution: DP

Subproblems : whether s3[0:i+j] can be formed by interleaving s1[0:i] and s2[0:j].

Time complexity: O(mn)

Space complexity: O(mn)

// Author: Huhaua

// Running time: 0 ms

class Solution {

public:

bool isInterleave(string s1, string s2, string s3) {

int l1 = s1.length();

int l2 = s2.length();

int l3 = s3.length();

if (l1 + l2 != l3) return false;

// dp[i][j]: whehter s3[0:i+j] is a interleva of s1[0:i] and s2[0:j]

vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1));

dp[0][0] = true;

for (int i = 0; i <= l1; ++i)

for (int j = 0; j <= l2; ++j) {

if (i > 0) dp[i][j] |= dp[i - 1][j] && s1[i - 1] == s3[i + j - 1];

if (j > 0) dp[i][j] |= dp[i][j - 1] && s2[j - 1] == s3[i + j - 1];

}

return dp[l1][l2];

}

};

Recursion + Memorization

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

bool isInterleave(string s1, string s2, string s3) {

m_ = vector<vector<int>>(s1.length() + 1, vector<int>(s2.length() + 1, INT_MIN));

return dp(s1, s1.length(), s2, s2.length(), s3, s3.length());

}

private:

// m_[i][j]: whehter s3[0:i+j] is a interleva of s1[0:i] and s2[0:j]

vector<vector<int>> m_;

bool dp(const string& s1, int l1, const string& s2, int l2, const string& s3, int l3) {

if (l1 + l2 != l3) return false;

if (l1 == 0 && l2 == 0) return true;

if (m_[l1][l2] != INT_MIN) return m_[l1][l2];

if (l1 > 0 & s3[l3 - 1] == s1[l1 - 1] && dp(s1, l1 - 1, s2, l2, s3, l3 - 1)

||l2 > 0 & s3[l3 - 1] == s2[l2 - 1] && dp(s1, l1, s2, l2 - 1, s3, l3 - 1))

m_[l1][l2] = 1;

else

m_[l1][l2] = 0;

return m_[l1][l2];

}

};

Posts tagged as “interleaving”

花花酱 LeetCode 1417. Reformat The String

Solution: Two streams

C++

花花酱 LeetCode 97. Interleaving String

Problem

Solution: DP