Posts tagged as “string”

花花酱 LeetCode 821. Shortest Distance to a Character

By zxi on April 22, 2018

Problem

题目大意：输出字符串的每个字符到一个指定字符的对短距离。

https://leetcode.com/problems/shortest-distance-to-a-character/description/

Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.

Example 1:

Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

Note:

S string length is in [1, 10000].
C is a single character, and guaranteed to be in string S.
All letters in S and C are lowercase.

Solution: Two Pass

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 14 ms

class Solution {

public:

vector<int> shortestToChar(string S, char C) {

const int n = S.length();

vector<int> ans(n, INT_MAX);

int index = -1;

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

if (S[i] == C) index = i;

if (index < 0) continue;

ans[i] = abs(i - index);

}

index = -1;

for (int i = n - 1; i >= 0; --i) {

if (S[i] == C) index = i;

if (index < 0) continue;

ans[i] = min(ans[i], abs(i - index));

}

return ans;

}

};

// Author: Huahua

// Running time: 14 ms

class Solution {

public:

vector<int> shortestToChar(string S, char C) {

const int n = S.length();

vector<int> indices(2 * n); // 0, 1, ..., n - 1, n - 1, n - 2, ..., 0

std::iota(indices.begin(), indices.begin() + n, 0);

std::iota(indices.rbegin(), indices.rbegin() + n, 0);

vector<int> ans(n, INT_MAX);

int index = -n;

for (int i : indices) {

if (S[i] == C) index = i;

ans[i] = min(ans[i], abs(i - index));

}

return ans;

}

};

花花酱 LeetCode 482. License Key Formatting

By zxi on April 16, 2018

Problem

题目大意：把序列号格式化，每组要求是K个字符（第一组 <= K），组和组之间用“-”分隔。

https://leetcode.com/problems/license-key-formatting/description/

You are given a license key represented as a string S which consists only alphanumeric character and dashes. The string is separated into N+1 groups by N dashes.

Given a number K, we would want to reformat the strings such that each group contains exactly K characters, except for the first group which could be shorter than K, but still must contain at least one character. Furthermore, there must be a dash inserted between two groups and all lowercase letters should be converted to uppercase.

Given a non-empty string S and a number K, format the string according to the rules described above.

Example 1:

Input: S = "5F3Z-2e-9-w", K = 4

Output: "5F3Z-2E9W"

Explanation: The string S has been split into two parts, each part has 4 characters.
Note that the two extra dashes are not needed and can be removed.

Example 2:

Input: S = "2-5g-3-J", K = 2

Output: "2-5G-3J"

Explanation: The string S has been split into three parts, each part has 2 characters except the first part as it could be shorter as mentioned above.

Note:

The length of string S will not exceed 12,000, and K is a positive integer.
String S consists only of alphanumerical characters (a-z and/or A-Z and/or 0-9) and dashes(-).
String S is non-empty.

Solution

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

string licenseKeyFormatting(string S, int K) {

string s;

for (char c : S)

if (c != '-') s.push_back(toupper(c));

int first = s.length() % K;

string ans = s.substr(0, first);

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

if (i % K == 0 && (i + first)) ans += '-';

ans.push_back(s[i + first]);

}

return ans;

}

};

花花酱 LeetCode 819. Most Common Word

By zxi on April 14, 2018

Problem

题目大意：找出一个段落中出现次数最多的单词。

https://leetcode.com/problems/most-common-word/description/

Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words. It is guaranteed there is at least one word that isn’t banned, and that the answer is unique.

Words in the list of banned words are given in lowercase, and free of punctuation. Words in the paragraph are not case sensitive. The answer is in lowercase.

Example:
Input: 
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

Note:

1 <= paragraph.length <= 1000.
1 <= banned.length <= 100.
1 <= banned[i].length <= 10.
The answer is unique, and written in lowercase (even if its occurrences in paragraph may have uppercase symbols, and even if it is a proper noun.)
paragraph only consists of letters, spaces, or the punctuation symbols !?',;.
Different words in paragraph are always separated by a space.
There are no hyphens or hyphenated words.
Words only consist of letters, never apostrophes or other punctuation symbols.

Solution: Hashtable

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

string mostCommonWord(string paragraph, vector<string>& banned) {

unordered_set<string> b(banned.begin(), banned.end());

unordered_map<string, int> counts;

const string pattern = "!?',;. ";

int best = 0;

string ans;

const int n = paragraph.size();

string word;

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

if (i == n || pattern.find(paragraph[i]) != string::npos) {

if (++counts[word] > best && !b.count(word) && word.size() > 0) {

best = counts[word];

ans = word;

}

word.clear();

} else {

word += tolower(paragraph[i]);

}

return ans;

}

};

花花酱 LeetCode 816. Ambiguous Coordinates

By zxi on April 14, 2018

Problem

题目大意：把一串数字分成两段，输出所有合法的分法（可以加小数点）。

https://leetcode.com/problems/ambiguous-coordinates/description/

We had some 2-dimensional coordinates, like "(1, 3)" or "(2, 0.5)". Then, we removed all commas, decimal points, and spaces, and ended up with the string S. Return a list of strings representing all possibilities for what our original coordinates could have been.

Our original representation never had extraneous zeroes, so we never started with numbers like “00”, “0.0”, “0.00”, “1.0”, “001”, “00.01”, or any other number that can be represented with less digits. Also, a decimal point within a number never occurs without at least one digit occuring before it, so we never started with numbers like “.1”.

The final answer list can be returned in any order. Also note that all coordinates in the final answer have exactly one space between them (occurring after the comma.)

Example 1:
Input: "(123)"
Output: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]

Example 2:
Input: "(00011)"
Output:  ["(0.001, 1)", "(0, 0.011)"]
Explanation: 
0.0, 00, 0001 or 00.01 are not allowed.

Example 3:
Input: "(0123)"
Output: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]

Example 4:
Input: "(100)"
Output: [(10, 0)]
Explanation: 
1.0 is not allowed.

Solution: Brute Force

Time complexity: O(n^3)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

vector<string> ambiguousCoordinates(string S) {

vector<string> ans;

int n = S.length();

for (int l1 = 1; l1 <= n - 3; ++l1) {

int l2 = n - l1 - 2;

string s1 = S.substr(1, l1);

string s2 = S.substr(l1 + 1, l2);

if (valid(s1) && valid(s2))

ans.push_back("(" + s1 + ", " + s2 + ")");

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

string ts1 = s1;

if (i > 0) ts1.insert(i, ".");

if (!valid(ts1)) continue;

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

if (i == 0 && j == 0) continue;

string ts2 = s2;

if (j > 0) ts2.insert(j, ".");

if (!valid(ts2)) continue;

ans.push_back("(" + ts1 + ", " + ts2 + ")");

}

return ans;

}

private:

bool valid(const string& s) {

bool p = false; // has "."

bool d = false; // has digits in front of "."

int zeros = 0; // leading zeros

int i = 0;

while (s[zeros] == '0' && zeros < s.length()) ++zeros;

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

if (!p && isdigit(s[i])) d = true;

if (s[i] == '.') p = true;

}

if (zeros == 1 && s != "0" && !p || zeros > 1) return false;

if (p && (s.back() == '0' || s.back() == '.' || zeros > 0 && d)) return false;

return true;

}

};

花花酱 LeetCode 331. Verify Preorder Serialization of a Binary Tree

By zxi on April 13, 2018

Problem

题目大意：验证二叉树前序遍历的序列化是否合法。

https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/description/

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where #represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character '#' representing nullpointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".

Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true

Example 2:
"1,#"
Return false

Example 3:
"9,#,#,1"
Return false

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solution: Recursion

If a node is not null, it must has two children, thus verify left subtree and right subtree recursively.
If a not is null, the current char must be ‘#’

Time complexity: O(n)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 5 ms

class Solution {

public:

bool isValidSerialization(string preorder) {

int pos = 0;

return isValid(preorder, pos) && pos == preorder.length();

}

private:

bool isValid(const string& s, int& pos) {

if (pos >= s.length()) return false;

if (isdigit(s[pos])) {

while (isdigit(s[pos])) ++pos;

return isValid(s, ++pos) && isValid(s, ++pos);

}

return s[pos++] == '#';

}

};