String-Easy
Abstract： 更新部分
Easy难度 string相关题解
13. Roman to Integer
解法一：Hash表
优先判定两个字符的值，其他没什么可说的
class Solution {
public int romanToInt(String s) {
Map<String, Integer> map = new HashMap<>();
map.put("I", 1);
map.put("IV", 4);
map.put("V", 5);
map.put("IX", 9);
map.put("X", 10);
map.put("XL", 40);
map.put("L", 50);
map.put("XC", 90);
map.put("C", 100);
map.put("CD", 400);
map.put("D", 500);
map.put("CM", 900);
map.put("M", 1000);
int ans=0;
for(int i=0;i<s.length();i++){
if(i+1<s.length() && map.containsKey(s.substring(i,i+2))){
ans+=map.get(s.substring(i,i+2));
i++;
}
else ans+=map.get(s.substring(i,i+1));
}
return ans;
}
}
14. Longest Common Prefix
解法一：线性扫描（从前往后）
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length==0 || strs==null){return "";}
String common="";
int min_len=Integer.MAX_VALUE;
for(String s:strs){min_len=Math.min(min_len,s.length());} //先找最小长度min_len
for(int curr=0;curr<min_len;curr++){
char c=strs[0].charAt(curr); //以第一个为准
for(String s:strs){if(s.charAt(curr)!=c)return common;}
common+=c;
}
return common;
}
}
[改进版]
- String ：改进了String的操作相关，String重载的 +操作 相当耗时，因此不使用字符串拼接，而是substring 的方法
- 遍历： 根本不需要找到最短的字符串，只要遍历时多判断一次是否超出就行了
- 效果： 12ms ->2ms
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length==0 || strs==null){return "";}
for(int curr=0;curr<strs[0].length();curr++){
char c=strs[0].charAt(curr);
for(String s:strs){
if(s.length()==curr || s.charAt(curr)!=c) //新增s.length()==curr判断一下就行
return strs[0].substring(0,curr); //改为substring,String+操作是相当费时的
}
}
return strs[0];
}
}
解法二：线性扫描（从后往前）
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++)
while (strs[i].indexOf(prefix) != 0) { //以第一个为准
prefix = prefix.substring(0, prefix.length() - 1); //如果不满足，每次缩小一个字符
if (prefix.isEmpty()) return ""; //直到为空
}
return prefix;
}
20. Valid Parentheses
解法一：栈（标准解法）
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for(int curr=0;curr<s.length();curr++){
char c=s.charAt(curr);
if(c=='(' || c=='[' || c=='{') //如果是左括号，压入栈中
stack.push(c);
else if(c==')'){ //如果是右括号，检查栈是否为空，不为空的话检查是否匹配
if(stack.isEmpty() || stack.pop()!='(')return false; //注意isEmpty在前
}
else if(c==']'){
if(stack.isEmpty() || stack.pop()!='[')return false;
}
else if(c=='}'){
if(stack.isEmpty() || stack.pop()!='{')return false;
}
}
return stack.isEmpty();//最后如果栈空则为ture,否则为false
}
}
28. Implement strStr()
解法一：猥琐API法（太脏了，自裁）
class Solution {
public int strStr(String haystack, String needle) {
return haystack.indexOf(needle); //这题要实现的就是indexOf的功能
}
}
解法二：暴力匹配
class Solution {
public int strStr(String haystack, String needle) {
//以下三者均会卡掉for循环，需要特别处理，且equals要第一个判定，否则第二条需要进一步限定
if(haystack.equals(needle))return 0; //字典等于词
if(haystack.length()==0)return -1; //字典为空
if(needle.length()==0) return 0; //词为空
//注意curr_hay<haystack.length()-needle.length()+1，必须+1，否则匹配不到最后一位
for(int curr_hay=0;curr_hay<haystack.length()-needle.length()+1;curr_hay++){
for(int curr_nee=0;curr_nee<needle.length();curr_nee++){
if(haystack.charAt(curr_hay+curr_nee)!=needle.charAt(curr_nee))
break;
if(curr_nee==needle.length()-1)//匹配到最后一个依然正确，返回此时的curr_hay
return curr_hay;
}
}
return -1; //没找到则返回-1
}
}
解法三：KMP（以后再说吧）
//问就是不会
58. Length of Last Word
要点分析
- 特殊情况：末尾有空格
- 如何找到最后一个空格？
- 连续空格怎么处理？
解法一：分段切割
- 缺点：substring耗时，trim耗时
class Solution {
public int lengthOfLastWord(String s) {
s=s.trim(); //开局剪切，保证末尾没有空格
String res=s;
for(int i=0;i<s.length();i++){
if(s.charAt(i)==' ')res=s.substring(i+1,s.length()); //每遇到一个空格，把前面的砍掉
}
return res.length(); //最后的长度即为所求
}
}
- 改进版，从后往前切割，大大节省时间
class Solution {
public int lengthOfLastWord(String s) {
s=s.trim(); //开局剪切，保证末尾没有空格
String res=s;
for(int i=s.length()-1;i>-1;i--){ //从后往前砍
if(s.charAt(i)==' '){return s.substring(i+1,s.length());}
}
return res.length(); //最后的长度即为所求
}
}
38. Count and Say
解法一：直接模拟
就挨着数呗
class Solution {
public:
string countAndSay(int n) {
if(n == 1) return "1";
return count(n - 1, "1");
}
string count(int n, string curr) {
if(n == 0) return curr;
vector<int> res;
int cnt = 1, len = curr.length();
for(int i = 0; i < len; i++) {
if(i + 1 < len && curr[i] == curr[i + 1])
cnt++;
else {
res.push_back(cnt);
res.push_back(curr[i] - '0');
cnt = 1;
}
}
curr.clear();
for(int i : res)
curr += to_string(i);
return count(n - 1, curr);
}
};
解法二：打表
纯属半夜无聊
class Solution {
public:
string countAndSay(int n) {
return findFromTable(n);
}
string findFromTable(int n) {
if (n == 1) return "1";
if (n == 2) return "11";
if (n == 3) return "21";
if (n == 4) return "1211";
if (n == 5) return "111221";
if (n == 6) return "312211";
if (n == 7) return "13112221";
if (n == 8) return "1113213211";
if (n == 9) return "31131211131221";
if (n == 10) return "13211311123113112211";
if (n == 11) return "11131221133112132113212221";
if (n == 12) return "3113112221232112111312211312113211";
if (n == 13) return "1321132132111213122112311311222113111221131221";
if (n == 14) return "11131221131211131231121113112221121321132132211331222113112211";
if (n == 15) return "311311222113111231131112132112311321322112111312211312111322212311322113212221";
if (n == 16) return "132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211";
if (n == 17) return "11131221131211132221232112111312212321123113112221121113122113111231133221121321132132211331121321231231121113122113322113111221131221";
if (n == 18) return "31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211";
if (n == 19) return "1321132132211331121321231231121113112221121321132122311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221";
if (n == 20) return "11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211";
if (n == 21) return "311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311122122111312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221131112311311121321122112132231121113122113322113111221131221";
if (n == 22) return "132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113213221133122112231131122211211131221131112311332211211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211";
if (n == 23) return "111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121113222123112221221321132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221";
if (n == 24) return "3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211";
if (n == 25) return "132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113213221132213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221";
if (n == 26) return "1113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123211211131211121311121321123113111231131122112213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122113221122112133221121113122113121113222123211211131211121311121321123113213221121113122113121113222113221113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211";
if (n == 27) return "31131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213122112311311123112111331121113122112132113311213211321222122111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311123113322113223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331221122311311222112111312211311123113322112132113213221133122211332111213112221133211322112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312111322211213111213122112132113121113222112132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212321121113121112133221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213212312311211131122211213211331121321122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311222113111221221113122112132113121113222112132113213221133122211332111213322112132113213221132231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221";
if (n == 28) return "13211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221232112111312211312113211223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321322113311213212322211322132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212311322123123112111321322123122113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132132211331221122311311222112111312211311123113322112111312211312111322212311322123123112112322211211131221131211132221132213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211";
if (n == 29) return "11131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221232112111312111213322112131112131221121321131211132221121321132132212321121113121112133221121321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122111213122112311311222113111221131221221321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212321121113121112133221132211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112132132112211131221131211132221121321132132212321121113121112133221123113112221131112311332111213211322111213111213211231131211132211121311222113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131211131221223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112211213322112312321123113213221123113112221133112132123222112311311222113111231132231121113112221121321133112132112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212311222122132113213221123113112221133112132123222112311311222113111231133211121321132211121311121321122112133221123113112221131112311332211322111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221";
if (n == 30) return "3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211";
return "No ans!";
}
};
67. Add Binary
解法一：模拟
模拟加法，不用多说了吧
class Solution {
public:
string addBinary(string a, string b) {
int len1 = a.length(), len2 = b.length();
if(len1 < len2) addZero(a, len2 - len1);
else if(len2 < len1) addZero(b, len1 - len2);
int carry = 0, len = std::max(len1, len2);
for(int i = len - 1; i > -1; i--) {
int val = a[i] + b[i] - 2 * '0' + carry;
carry = val / 2;
val %= 2;
a[i] = val + '0';
}
if(carry == 1) a = '1' + a;
return a;
}
void addZero(string& s, int len) {
for(int i = 0; i < len; i++)
s = '0' + s;
}
};
290. Word Pattern
解法一：单哈希
写的很乱
- 先分割string
- 记录pattern对应的索引
- 对比vector中每个元素是否等于模式串所指的位置元素
- 还要判断一下模式串之间是否不同，即a所指的和b所指的必须不同（逻辑上其实也可以认为相同，但是这题认为是不同的）
class Solution {
public:
bool wordPattern(string pattern, string str) {
vector<string> v = split(str);
if(pattern.length() != v.size()) return false;
unordered_map<char, int> map;
for(int i = 0; i < pattern.length(); i++) {
if(map.find(pattern[i]) == map.end())
map[pattern[i]] = i;
if(v[map[pattern[i]]] != v[i]) return false;
}
string s = "";
for(auto k : map) {
int idx = k.second;
string ns = v[idx];
if(ns == s) return false;
s = ns;
}
return true;
}
vector<string> split(string str) {
vector<string> v;
string tmp = "";
for(int i = 0; i < str.length(); i++) {
if(str[i] == ' ') {
if(tmp.empty()) {
continue;
}
else {
v.push_back(tmp);
tmp.clear();
}
}
else tmp += str[i];
if(i == str.length() - 1 && !tmp.empty()) v.push_back(tmp);
}
return v;
}
};
分割字符串的简单写法
vector<string> split(string str) {
vector<string> v;
istringstream ss(str);
string s;
while(ss >> s) v.push_back(s);
return v;
}
解法二：双哈希
看了评论发现大家都是双哈希的。。的确简单不少
class Solution {
public:
bool wordPattern(string pattern, string str) {
unordered_map<char, int> cmap;
unordered_map<string, int> smap;
vector<string> v = split(str);
if(pattern.length() != v.size()) return false;
for(int i = 0; i < v.size(); i++) {
if(smap[v[i]] != cmap[pattern[i]]) return false;
else
smap[v[i]] = cmap[pattern[i]] = i + 1;
}
return true;
}
vector<string> split(string str) {
vector<string> v;
istringstream ss(str);
string s;
while(ss >> s) v.push_back(s);
return v;
}
};