Posts published in “String”

花花酱 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 557 Reverse Words in a String III

By zxi on March 2, 2018

题目大意：独立反转字符串中的每个单词。

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

1 2	Input: "Let's take LeetCode contest" Output: "s'teL ekat edoCteeL tsetnoc"

Note: In the string, each word is separated by single space and there will not be any extra space in the string.

Idea: Brute Force

C++

// Author: Huahua

// Running time: 23 ms

class Solution {

public:

string reverseWords(string s) {

int index = 0;

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

if (i == s.length() || s[i] == ' ') {

std::reverse(s.begin() + index, s.begin() + i);

index = i + 1;

}

return s;

}

};

Python3

"""

Author: Huahua

Running time: 44 ms (beats 100%)

"""

class Solution:

def reverseWords(self, s):

return ' '.join(map(lambda x: x[::-1], s.split(' ')))

花花酱 LeetCode 468. Validate IP Address

By zxi on March 1, 2018

题目大意：给你一个字符串，让你判断是否是合法的ipv4或者ipv6地址，都不合法返回Neighter.

Write a function to check whether an input string is a valid IPv4 address or IPv6 address or neither.

IPv4 addresses are canonically represented in dot-decimal notation, which consists of four decimal numbers, each ranging from 0 to 255, separated by dots (“.”), e.g.,172.16.254.1;

Besides, leading zeros in the IPv4 is invalid. For example, the address 172.16.254.01 is invalid.

IPv6 addresses are represented as eight groups of four hexadecimal digits, each group representing 16 bits. The groups are separated by colons (“:”). For example, the address 2001:0db8:85a3:0000:0000:8a2e:0370:7334 is a valid one. Also, we could omit some leading zeros among four hexadecimal digits and some low-case characters in the address to upper-case ones, so 2001:db8:85a3:0:0:8A2E:0370:7334 is also a valid IPv6 address(Omit leading zeros and using upper cases).

However, we don’t replace a consecutive group of zero value with a single empty group using two consecutive colons (::) to pursue simplicity. For example, 2001:0db8:85a3::8A2E:0370:7334 is an invalid IPv6 address.

Besides, extra leading zeros in the IPv6 is also invalid. For example, the address 02001:0db8:85a3:0000:0000:8a2e:0370:7334 is invalid.

Note: You may assume there is no extra space or special characters in the input string.

Example 1:

Input: "172.16.254.1"

Output: "IPv4"

Explanation: This is a valid IPv4 address, return "IPv4".

Example 2:

Input: "2001:0db8:85a3:0:0:8A2E:0370:7334"

Output: "IPv6"

Explanation: This is a valid IPv6 address, return "IPv6".

Example 3:

Input: "256.256.256.256"

Output: "Neither"

Explanation: This is neither a IPv4 address nor a IPv6 address.

Solution 1: String / Brute force

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool isV4Num(string n) {

if (n.length() > 3 || n.empty()) return false;

std::reverse(n.begin(), n.end());

int a = 0;

int f = 1;

for (char c : n) {

if (!isdigit(c)) return false;

if (c == '0' && f > 1) return false;

a += (c - '0') * f;

f *= 10;

}

return a >= 0 && a <= 255;

}

bool isV6Num(string n) {

if (n.length() > 4 || n.empty()) return false;

std::reverse(n.begin(), n.end());

int a = 0;

int f = 1;

for (char c : n) {

if (isdigit(c))

a += (c - '0') * f;

else if (c >= 'a' && c <= 'f' || c >= 'A' && c <= 'Z')

a += (tolower(c) - 'a' + 10) * f;

else

return false;

f *= 16;

}

return a >= 0 && a < (1 << 16);

}

string validIPAddress(string IP) {

bool isIPv4 = true;

bool isIPv6 = true;

string cur;

int seg = 0;

for (char c: IP) {

if (c == '.') { ++seg; isIPv6 = false; isIPv4 &= isV4Num(cur); cur.clear(); }

else if (c == ':') { ++seg; isIPv4 = false; isIPv6 &= isV6Num(cur); cur.clear(); }

else cur += c;

}

isIPv4 &= isV4Num(cur) && seg == 3;

isIPv6 &= isV6Num(cur) && seg == 7;

return isIPv4 ? "IPv4" : (isIPv6 ? "IPv6" : "Neither");

}

};

花花酱 LeetCode 791. Custom Sort String

By zxi on February 24, 2018

题目大意：给你字符的顺序，让你排序一个字符串。

S and T are strings composed of lowercase letters. In S, no letter occurs more than once.

S was sorted in some custom order previously. We want to permute the characters of T so that they match the order that S was sorted. More specifically, if x occurs before y in S, then x should occur before y in the returned string.

Return any permutation of T (as a string) that satisfies this property.

Example :

Input:

S = "cba"

T = "abcd"

Output: "cbad"

Explanation:

"a", "b", "c" appear in S, so the order of "a", "b", "c" should be "c", "b", and "a".

Since "d" does not appear in S, it can be at any position in T. "dcba", "cdba", "cbda" are also valid outputs.

Note:

S has length at most 26, and no character is repeated in S.
T has length at most 200.
S and T consist of lowercase letters only.

Solution 1: HashTable + Sorting

Store the order of char in a hashtable
Sort the string based on the order

Time complexity: O(nlogn)

Space complexity: O(128)

// Author: Huahua

// Running time: 2 ms

class Solution {

public:

string customSortString(string S, string T) {

vector<int> order(128, INT_MAX);

int i = 0;

for (char c: S)

if (order[c] == INT_MAX) order[c] = ++i;

std::sort(T.begin(), T.end(), [&order](const char c1, const char c2){

return order[c1] < order[c2];

});

return T;

}

};

花花酱 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;

}

};