Posts tagged as “string”

花花酱 LeetCode 696. Count Binary Substrings

By zxi on March 6, 2018

题目大意：给你一个二进制的字符串，问有多少子串的0个数量等于1的数量。

Problem:

https://leetcode.com/problems/count-binary-substrings/description/

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: "00110011"

Output: 6

Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".

Notice that some of these substrings repeat and are counted the number of times they occur.

Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

Example 2:

Input: "10101"

Output: 4

Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

Note:

s.length will be between 1 and 50,000.
s will only consist of “0” or “1” characters.

Solution 0: Search

Try all possible substrings and check whether it’s a valid one or not.

Time complexity O(2^n * n) TLE

Space complexity: O(n)

Solution 1: Running Length

For S = “000110”, there are two virtual blocks “[00011]0” and “000[110]” which contains consecutive 0s and 1s or (1s and 0s)

Keep tracking of the running length of 0, 1 for each block

“00011” => ‘0’: 3, ‘1’:2

ans += min(3, 2) => ans = 2 (“[0011]”, “0[01]1”)

“110” => ‘0’: 1, ‘1’: 2

ans += min(1, 2) => ans = 3 (“[0011]”, “0[01]1”, “1[10]”)

We can reuse part of the running length from last block.

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 43 ms

class Solution {

public:

int countBinarySubstrings(string s) {

vector<int> lens(128, 0);

int i = 0;

int l = 0;

int ans = 0;

while (true) {

while (i < s.length() && s[i] == s[l]) ++i;

lens[s[l]] = i - l;

ans += min(lens['0'], lens['1']);

if (i == s.length()) break;

lens[s[i]] = 0;

l = i;

}

return ans;

}

};

花花酱 LeetCode 794. Valid Tic-Tac-Toe State

By zxi on March 3, 2018

题目大意：判断一个井字棋的棋盘是否有效。

A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The board is a 3 x 3 array, and consists of characters " ", "X", and "O". The ” ” character represents an empty square.

Here are the rules of Tic-Tac-Toe:

Players take turns placing characters into empty squares (” “).
The first player always places “X” characters, while the second player always places “O” characters.
“X” and “O” characters are always placed into empty squares, never filled ones.
The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
The game also ends if all squares are non-empty.
No more moves can be played if the game is over.

Example 1:

Input: board = ["O ", " ", " "]

Output: false

Explanation: The first player always plays "X".

Example 2:

Input: board = ["XOX", " X ", " "]

Output: false

Explanation: Players take turns making moves.

Example 3:

Input: board = ["XXX", " ", "OOO"]

Output: false

Example 4:

Input: board = ["XOX", "O O", "XOX"]

Output: true

Note:

board is a length-3 array of strings, where each string board[i] has length 3.
Each board[i][j] is a character in the set {" ", "X", "O"}.

Idea: Verify all rules

C++

class Solution {

public:

bool validTicTacToe(vector<string>& board) {

int x = 0;

int o = 0;

int wins_x = getWins(board, 'X', x);

int wins_o = getWins(board, 'O', o);

return wins_x + wins_o <= 1 && x >= o + wins_x && x <= o + 1 - wins_o;

}

private:

int getWins(const vector<string>& board, char p, int& count) {

vector<string> rows(3);

string diag1, diag2;

for (int i = 0; i < 3; ++i) {

diag1 += board[i][i];

diag2 += board[i][2 - i];

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

char c = board[i][j];

rows[j] += c;

count += c == p;

}

string win(3, p);

int wins = (diag1 == win) + (diag2 == win);

for (int i = 0; i < 3; ++i) {

wins += rows[i] == win;

wins += board[i] == win;

}

return wins;

}

};

花花酱 LeetCode 788 Rotated Digits

By zxi on February 24, 2018

题目大意：

给一个字符串，独立旋转每个数字180°，判断得到的新字符串是否合法。

出现数字3,4,7一定不合法
新字符串 == 原来字符串不合法

X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X. A number is valid if each digit remains a digit after rotation. 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other; 6 and 9 rotate to each other, and the rest of the numbers do not rotate to any other number.

Now given a positive number N, how many numbers X from 1 to N are good?

Example:

Input: 10

Output: 4

Explanation:

There are four good numbers in the range [1, 10] : 2, 5, 6, 9.

Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.

Note:

N will be in range [1, 10000].

Solution 1: Brute Force

Time complexity: O(nlogn)

C++

// Author: Huahua

// Running time: 21 ms

class Solution {

public:

int isValid(int n) {

string s = to_string(n);

string t(s);

for (int i = 0; i < s.length(); ++i) {

if (s[i] == '3' || s[i] == '4' || s[i] == '7')

return 0;

else if (s[i] == '2') t[i] = '5';

else if (s[i] == '5') t[i] = '2';

else if (s[i] == '6') t[i] = '9';

else if (s[i] == '9') t[i] = '6';

}

return t != s;

}

int rotatedDigits(int N) {

int ans = 0;

for (int i = 1; i <= N; ++i)

ans += isValid(i);

return ans;

}

};

Bit Operation

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int isValid(int n) {

constexpr int kInValidMask = (1 << 3) | (1 << 4) | (1 << 7);

constexpr int kValidMask = (1 << 2) | (1 << 5) | (1 << 6) | (1 << 9);

int valid = 0;

while (n > 0) {

int r = 1 << (n % 10);

if (r & kInValidMask)

return 0;

else if (r & kValidMask)

valid = 1;

n /= 10;

}

return valid;

}

int rotatedDigits(int N) {

int ans = 0;

for (int i = 1; i <= N; ++i)

ans += isValid(i);

return ans;

}

};

花花酱 LeetCode 771. Jewels and Stones

By zxi on February 2, 2018

题目大意：给你宝石的类型，再给你一堆石头，返回里面宝石的数量。

Problem:

You’re given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

Input: J = "z", S = "ZZ"
Output: 0

Note:

S and J will consist of letters and have length at most 50.
The characters in J are distinct.

Solution 1: HashTable

Time complexity: O(|J| + |S|)

Space complexity: O(128) / O(|J|)

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int numJewelsInStones(string J, string S) {

std::vector<int> f(128, 0);

int ans = 0;

for (const char j : J)

f[j] = 1;

for (const char s : S)

ans += f[s] & 1;

return ans;

}

};

C++ v2

// Author: Huahua

// Running time: 10 ms

class Solution {

public:

int numJewelsInStones(const string& J, const string& S) {

std::set<char> f(J.begin(), J.end());

return std::count_if(S.begin(), S.end(),

[&f](const char c) { return f.count(c); });

}

};

Java

// Author: Huahua

// Running time: 18 ms

class Solution {

public int numJewelsInStones(String J, String S) {

int[] f = new int[128];

for (final char c : J.toCharArray())

f[c] = 1;

int ans = 0;

for (final char c : S.toCharArray())

ans += f[c];

return ans;

}

Python

"""

Author: Huahua

Running time: 43 ms

"""

class Solution(object):

def numJewelsInStones(self, J, S):

f = set(J)

return sum([s in f for s in S])

花花酱 LeetCode 763. Partition Labels

By zxi on January 25, 2018

题目大意：把字符串分割成尽量多的不重叠子串，输出子串的长度数组。要求相同字符只能出现在一个子串中。

Problem:

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Input: S = "ababcbacadefegdehijhklij"

Output: [9,7,8]

Explanation:

The partition is "ababcbaca", "defegde", "hijhklij".

This is a partition so that each letter appears in at most one part.

A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

Solution 0: Brute Force

Time complexity: O(n^2)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

vector<int> partitionLabels(string S) {

vector<int> ans;

size_t start = 0;

size_t end = 0;

for (size_t i = 0; i < S.size(); ++i) {

end = max(end, S.find_last_of(S[i]));

if (i == end) {

ans.push_back(end - start + 1);

start = end + 1;

}

return ans;

}

};

Python

"""

Author: Huahua

Running time : 48 ms

"""

class Solution:

def partitionLabels(self, S):

ans = []

start, end = 0, 0

for i in range(len(S)):

end = max(end, S.rfind(S[i]))

if i == end:

ans.append(end - start + 1)

start = end + 1

return ans

Solution 1: Greedy

Time complexity: O(n)

Space complexity: O(26/128)

C++

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

vector<int> partitionLabels(string S) {

vector<int> last_index(128, 0);

for (int i = 0; i < S.size(); ++i)

last_index[S[i]] = i;

vector<int> ans;

int start = 0;

int end = 0;

for (int i = 0; i < S.size(); ++i) {

end = max(end, last_index[S[i]]);

if (i == end) {

ans.push_back(end - start + 1);

start = end + 1;

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 16 ms

class Solution {

public List<Integer> partitionLabels(String S) {

int lastIndex[] = new int[128];

for (int i = 0; i < S.length(); ++i)

lastIndex[(int)S.charAt(i)] = i;

List<Integer> ans = new ArrayList<>();

int start = 0;

int end = 0;

for (int i = 0; i < S.length(); ++i) {

end = Math.max(end, lastIndex[(int)S.charAt(i)]);

if (i == end) {

ans.add(end - start + 1);

start = end + 1;

}

return ans;

}

Python3

"""

Author: Huahua

Running time: 78 ms

"""

class Solution:

def partitionLabels(self, S):

last_index = {}

for i, ch in enumerate(S):

last_index[ch] = i

start = end = 0

ans = []

for i, ch in enumerate(S):

end = max(end, last_index[ch])

if i == end:

ans.append(end - start + 1)

start = end + 1

return ans