- Add Strings
Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.
You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.
Example 1:
Input: num1 = "11", num2 = "123"
Output: "134"Example 2:
Input: num1 = "456", num2 = "77"
Output: "533"Example 3:
Input: num1 = "0", num2 = "0"
Output: "0"code
```C++ class Solution { public: string addStrings(string num1, string num2) { int n1=num1.size()-1,n2=num2.size()-1,temp=0; string ans; while(n1>=0||n2>=0||temp!=0){ int x=n1>=0?(num1[n1]-'0'):0; int y=n2>=0?(num2[n2]-'0'):0; int sum=x+y+temp; ans.push_back('0'+sum%10); temp=sum/10; n1--; n2--; } int n=ans.size(); for(int i=0;i<n/2;i++){ temp=ans[i]; ans[i]=ans[n-1-i]; ans[n-1-i]=temp; } return ans; } };
# 409. Longest Palindrome
Given a string `s` which consists of lowercase or uppercase letters, return *the length of the **longest palindrome*** that can be built with those letters.
Letters are **case sensitive**, for example, `"Aa"` is not considered a palindrome here.
<a href="https://leetcode.cn/problems/longest-palindrome/?envType=study-plan&id=shu-ju-jie-gou-ji-chu&plan=data-structures&plan_progress=1hi0xhg">link</a>
**Example 1:**
Input: s = "abccccdd" Output: 7 Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.
**Example 2:**
Input: s = "a" Output: 1 Explanation: The longest palindrome that can be built is "a", whose length is 1.
## code
```C++
class Solution {
public:
int longestPalindrome(string s) {
int arr[128]={0};
for(char c:s){
arr[c]++;
}
int count=0;
for(int i=0;i<128;i++){
count+=arr[i]%2;
}
return count==0?s.size():(s.size()-count+1);
}
};290. Word Pattern
Given a pattern and a string s, find if s follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.
Example 1:
Input: pattern = "abba", s = "dog cat cat dog"
Output: trueExample 2:
Input: pattern = "abba", s = "dog cat cat fish"
Output: falseExample 3:
Input: pattern = "aaaa", s = "dog cat cat dog"
Output: falsecode
```c++ class Solution { public: bool wordPattern(string pattern, string s) { unordered_map<char,string> char2str; unordered_map<string,char> str2char; int m = s.length(); int i=0; for(char ch:pattern){ if(i>=m) return false; int j=i; while(j<m&&s[j]!=' ') j++; const string &temp = s.substr(i,j-i); if(str2char.count(temp)&&str2char[temp]!=ch){ return false; } if(char2str.count(ch)&&char2str[ch]!=temp){ return false; } str2char[temp]=ch; char2str[ch]=temp; i=j+1; } return i>=m; } };
# 763. Partition Labels
You are given a string `s`. We want to partition the string into as many parts as possible so that each letter appears in at most one part.
Note that the partition is done so that after concatenating all the parts in order, the resultant string should be `s`.
Return *a list of integers representing the size of these parts*.
<a href="https://leetcode.cn/problems/partition-labels/?envType=study-plan&id=shu-ju-jie-gou-ji-chu&plan=data-structures&plan_progress=1hi0xhg">link</a>
**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.
**Example 2:**
Input: s = "eccbbbbdec" Output: [10]
## code
```c++
class Solution {
public:
vector<int> partitionLabels(string s) {
int map[26]={0};
for(int i=0;i<s.length();i++){
map[s[i]-'a']=i;
}
vector<int> partition;
int start=0,end=0;
for(int i=0;i<s.length();i++){
end=max(end,map[s[i]-'a']);
if(i==end){
partition.push_back(end-start+1);
start=end+1;
}
}
return partition;
}
};49. Group Anagrams
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]Example 2:
Input: strs = [""]
Output: [[""]]Example 3:
Input: strs = ["a"]
Output: [["a"]]code
```C++
class Solution {
public:
vector<vector
# 43. Multiply Strings
Given two non-negative integers `num1` and `num2` represented as strings, return the product of `num1` and `num2`, also represented as a string.
**Note:** You must not use any built-in BigInteger library or convert the inputs to integer directly.
<a href="https://leetcode.cn/problems/multiply-strings/?envType=study-plan&id=shu-ju-jie-gou-ji-chu&plan=data-structures&plan_progress=1hi0xhg">link</a>
**Example 1:**
Input: num1 = "2", num2 = "3" Output: "6"
**Example 2:**
Input: num1 = "123", num2 = "456" Output: "56088"
## code
```C++
class Solution {
public:
string multiply(string num1, string num2) {
if(num1=="0"||num2=="0") return "0";
int m=num1.length(),n=num2.length();
string ans="0";
for(int i=n-1;i>=0;i--){
string curr;
int add=0,x=num2[i]-'0';
for(int j=n-1;j>i;j--){
curr.push_back(0);
}
for(int j=m-1;j>=0;j--){
int y=num1[j]-'0';
int prod=x*y+add;
curr.push_back(prod%10);
add=prod/10;
}
while(add!=0){
curr.push_back(add%10);
add/=10;
}
reverse(curr.begin(),curr.end());
for(auto& c:curr){
c+='0';
}
//cout<<curr<<endl;
ans=addString(ans,curr);
}
return ans;
}
string addString(string num1,string num2){
int add=0;
int i=num1.size()-1,j=num2.size()-1;
string ans;
while(i>=0||j>=0||add!=0){
int x=i>=0?(num1[i]-'0'):0;
int y=j>=0?(num2[j]-'0'):0;
int temp=x+y+add;
ans.push_back(temp%10+'0');
add=temp/10;
i--;
j--;
}
reverse(ans.begin(),ans.end());
return ans;
}
};187. Repeated DNA Sequences
The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'.
- For example,
"ACGAATTCCG"is a DNA sequence.
When studying DNA, it is useful to identify repeated sequences within the DNA.
Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.
Example 1:
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]Example 2:
Input: s = "AAAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]code
```c++
class Solution {
const int L=10;
public:
vector
# 5. Longest Palindromic Substring
Given a string `s`, return *the longest*
*palindromic*
*substring* in `s`.
<a href="https://leetcode.cn/problems/longest-palindromic-substring/?envType=study-plan&id=shu-ju-jie-gou-ji-chu&plan=data-structures&plan_progress=1hi0xhg">link</a>
**Example 1:**
Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.
**Example 2:**
Input: s = "cbbd" Output: "bb"
## code
```c++
class Solution {
public:
string longestPalindrome(string s) {
int n=s.length();
if(n<2) return s;
vector<vector<bool>> dp(n,vector<bool>(n));
int start=0,maxLen=1;
for(int i=0;i<n;i++){
dp[i][i]=true;
}
for(int L=2;L<=n;L++){
for(int i=0;i<n;i++){
int j=i+L-1;
if(j>=n) break;
if(s[i]!=s[j]){
dp[i][j]=false;
}else{
if(j-i<3){
dp[i][j]=true;
}else{
dp[i][j]=dp[i+1][j-1];
}
}
if(dp[i][j]&&j-i+1>maxLen){
maxLen=j-i+1;
start=i;
//cout<<11<<endl;
}
}
}
//cout<<start<<maxLen;
return s.substr(start,maxLen);
}
};