题目描述：给定一个由n个不重复非空字符串组成的数组，你需要按照以下规则为每个单词生成最小的缩写。
1.初始缩写由起始字母+省略字母的数量+结尾字母组成。
2.若存在冲突，亦即多于一个单词有同样的缩写，则使用更长的前缀代替首字母，直到从单词到缩写的映射唯一。
3.若缩写并不比原单词更短，则保留原样。
解析：若是两个字符串的缩写相同，我们就通过前缀树来求解每一个字符串的最短前缀。
public String addrecvString(String str, int i){
int n = str.length();
if (n <= i + 3)return str;
return str.substring(0, 1 + i) + (n - 2 - i) + str.charAt(n - 1);
}
public List<String> wordsAbbreviation(List<String> dict){
//1.构建map将字符串分组，拥有相同缩写的字符串被分到一组。
Map<String, List<IndexWord>> map = new HashMap<>();
String[] res = new String[dict.size()];
int index = 0;
for (String str : dict){
String tmp = addrecvString(str, 0);
if (!map.containsKey(tmp)){
map.put(tmp, new ArrayList<IndexWord>());
}
map.get(tmp).add(new IndexWord(str, index));
index++;
}
//2.遍历每一个组
for (List<IndexWord> group : map.values()){
TrieNode trie = new TrieNode();
//2.1遍历组中每一个字符串构建trieTree
for (IndexWord iw : group){
TrieNode cur = trie;
for (char ms : iw.word.substring(1).toCharArray()){
if (cur.children[ms - 'a'] == null){
cur.children[ms - 'a'] = new TrieNode();
}
cur.count++;
cur = cur.children[ms - 'a'];
}
}
//2.2遍历构建的trieTree，来确定最小前缀。
for (IndexWord iw : group){
TrieNode cur = trie;
int i = 0;
for (char ms : iw.word.substring(1).toCharArray()){
//若是count==1，则说明该节点只被访问过一次，符合最小前缀。
if (cur.count == 1)break;
cur = cur.children[ms - 'a'];
i++;
}
res[iw.index] = addrecvString(iw.word, i);
}
}
return Arrays.asList(res);
}
class TrieNode{
//前缀树节点，count记录当前节点有多少次被访问到
TrieNode[] children;
int count;
TrieNode(){
children = new TrieNode[26];
count = 0;
}
}
class IndexWord{
String word;
int index;
IndexWord(String str, int i){
word = str;
index = i;
}
}题目描述：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
解析：通过map记录每一个字符的下标，每次遇到重复的字符就找到该字符第一次出现的位置，并将窗口的左边界更新为该字符第一次出现的位置
public int lengthOfLongestSubstring(String s){
int res = 0;
char[] ss = s.toCharArray();
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int flag = -1;
for (int i = 0; i < ss.length; i++){
if (map.containsKey(ss[i]) && map.get(ss[i]) > flag){
flag = map.get(ss[i]);//更新窗口左边界
}
res = Math.max(res, i - flag);
if (res > ss.length - flag)break;
map.put(ss[i], i);
}
return res;
}题目描述：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
public String longestPalindrome(String s) {//manacher
if (s.length() == 0)return s;
char[] ss = getArray(s.toCharArray());
int[] num = new int[ss.length];
int pR = -1;
int index = -1;
int max = Integer.MIN_VALUE;
int left = 0;
for (int i = 0; i < num.length; i++){
num[i] = i >= pR? 1 :Math.min(num[2 * index - i], pR - i);
while(i + num[i] < ss.length && i - num[i] > -1 && ss[i + num[i]] == ss[i - num[i]]){
num[i]++;
}
if (i + num[i] > pR){
pR = i + num[i];
index = i;
}
if (max < num[i]){
max = num[i];
left = (i - num[i] + 1) / 2;
}
}
return s.substring(left, left + max - 1);
}
public char[] getArray(char[] ss){
char[] res = new char[ss.length * 2 + 1];
int index = 0;
for (int i = 0; i < res.length; i++){
res[i] = i%2==0?'#':ss[index++];
}
return res;
}题目描述：给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
解析：每次的遍历都会分为两种进行判断：
1.当前字符的下一个是不是'*'
1.1 两字符能匹配上,p字符匹配多次(s后移一位)或者是p字符匹配零次(p后移两位)
1.2 两字符不能匹配上，则p字符匹配零次(p后移两位)。
2.下一个不是'*'
或是两字符能匹配就继续匹配，否则直接结束。
public boolean isMatch(String s, String p) {
if (s == null || p == null)return false;
return run(s, 0, p, 0);
}
public boolean run(String s, int sIndex, String p, int pIndex){
if (sIndex == s.length() && pIndex == p.length())return true;
if (pIndex == p.length())return false;
if (pIndex + 1 < p.length() && p.charAt(pIndex + 1) == '*'){
if (sIndex != s.length() && (s.charAt(sIndex) == p.charAt(pIndex) || p.charAt(pIndex) == '.')){
return run(s, sIndex + 1, p, pIndex) || run(s, sIndex, p, pIndex + 2);
}else{
return run(s, sIndex, p, pIndex + 2);
}
}else{
if (sIndex != s.length() && (s.charAt(sIndex) == p.charAt(pIndex) || p.charAt(pIndex) == '.')){
return run(s, sIndex + 1, p, pIndex + 1);
}else{
return false;
}
}
}题目描述：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
public boolean isNumeric(char[] str) {
boolean hasE = false, hasDot = false, hasOpe = false;
for (int i = 0; i < str.length; i++){
if (str[i] == 'e' || str[i] == 'E'){
if (i == str.length - 1)return false;//e不能是最后一个
if (hasE)return false;//e不能出现两次
hasE = true;
}else if (str[i] == '+' || str[i] == '-'){
if (i > 0 && !hasOpe && !(str[i - 1] == 'e' || str[i - 1] == 'E'))return false;//+-第一次出现但不是开头前面必须是e（i>0是为了避开第一次出现在开头的情况）
if (hasOpe && !(str[i - 1] == 'e' || str[i - 1] == 'E'))return false;//第二次出现前面必须是e
hasOpe = true;
}else if (str[i] == '.'){
if (hasDot || hasE)return false;//小数点只能出现一次，且不能在e后面
hasDot = true;
}else{
if (str[i] < '0' || str[i] > '9')return false;//字符需要合法
}
}
return true;
}题目描述：请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
解析：维护一个数组，每当有字符插入的时候就在该数组对应位置+1来表示该字符来过几次；维护一个list，每当有新的字符加入就判断该字符之前有没有出现过，若是没有就将其加入到list底部。
private int[] map = new int[256];
private LinkedList<Character> arr = new LinkedList<Character>();
public void Insert(char ch)
{
map[ch]++;
if (map[ch] == 1)arr.addLast(ch);
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
if(arr.isEmpty())return '#';
char ch = arr.peek();
while (map[ch] != 1){
arr.pop();
if(arr.isEmpty())return '#';
ch = arr.peek();
}
return ch;
}题目描述：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
private String[] ss ={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
private List<String> res = new ArrayList<String>();
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0)return res;
run("", digits);
return res;
}
public void run(String str, String rest){
if (rest.length() == 0){
res.add(str);
}else{
String arr = ss[rest.charAt(0) - '2'];
for (int i = 0; i < arr.length(); i++){
run(str + arr.substring(i, i+1), rest.substring(1));
}
}
}