【JAVA】每日两道算法题0915_栈、字符串处理

向右看齐 2021-09-24 16:32 300阅读 0赞

题目：给定一个只包括 ‘(’，’)’，’\{’，’\}’，’\[’，’\]’ 的字符串，判断字符串是否有效。  
来源：力扣（LeetCode）

> 有效字符串需满足：  
> 1.左括号必须用相同类型的右括号闭合。  
> 2.左括号必须以正确的顺序闭合。  
> 3.空字符串可被认为是有效字符串。

标签：`栈`

思路：  
1.当字符串长度为奇数时，返回false;  
2.前面一直是左括号时，需要一个数据结构暂存这些等着被匹配的左括号。当右括号出现时，这些暂存的左括号以“后进先出”的方式被匹配。所以用“栈”这种数据结构去暂存等着被匹配的左括号。  
3.如果是左括号，执行压入栈。如果是右括号，判断当前栈顶是否是与之匹配的左括号。如果是的话，栈顶出栈。如果不是的话或者栈目前未空，则返回false。  
4.左右括号存储为map

代码实现：

class Solution{ 
    	public boolean isVaild(String s) { 
    		int len = s.length();
    		if (len % 2 == 1) { return false;}
    		Map<Character, Character> map = new HashMap<Character, Character>(){ { 
    			put(')', '(');
    			put(']', '[');
    			put('}', '{');
    		}};
    		LinkedList<Character> stack = new LinkedList<Character>();
    		for (int i = 0; i < len; i++) { 
    			char ch = s.charAt(i);
    			if(map.containsKey(ch)) { 
    				if (stack.isEmpty() || stack.peek() != map.get(ch)){ 
    					return false;
    					}
    				stack.pop();
    			}
    			else { 
    				stack.push(ch);
    			}
    		}
    		return stack.isEmpty();		
    	}
    }

题目：编写一个函数来查找字符串数组中的最长公共前缀。  
如果不存在公共前缀，返回空字符串 “”。

> 说明：所有输入只包含小写字母a-z

标签：`字符串`

思路：

*  横向比较  
    1.如果字符串数组为null或者长度为0，直接返回空字符串。  
    2.将最长公共前缀prefix的值设置为第一个字符串strs\[0\]，进行初始化。  
    3.遍历数组。依次比较prefix与strs\[i\]，得到最新的最长公共前缀作为新的prefix。  
    4.比较时，用到字符串切割函数substring（）.  
    代码实现：

class Solution { 
        public String longestCommonPrefix(String[] strs) { 
            if (strs == null || strs.length == 0) { return "";}
            String prefix = strs[0];
            for (int i = 1; i < strs.length; i++) { 
               prefix = getPrefix(prefix, strs[i]); 
            }
            return prefix;
        }
    
        private String getPrefix(String s1, String s2) { 
            int minLen = Math.min(s1.length(), s2.length());
            for (int i = 0; i< minLen; i++) { 
                if(s1.charAt(i) != s2.charAt(i)) { 
                    return s1.substring(0,i);   //返回字符串的前i位。
                }    
            }
            return s1.substring(0,minLen);
        }
    }

时间复杂度O(mn)

*  纵向比较  
    1.数组长度个字符串，依次比较字符串的第一位、第二位

class Solution { 
    	public String longestCommonPrefix(String[] strs) { 
    		int n = strs.length;
    		int len = strs[0].length;
    		if (strs == null || n == 0) { return '';}
    		for (int i = 0; i < len; i++) { 
    			char ch = strs[0].chatAt(i);
    			for (int j = 1; j < n; j++) { 
    				if (ch != strs[j].charAt(i) || i == strs[j].length()) { 
    					return strs[0].substring(0,i);
    				}
    			}
    		}
    		return str[0];
    	}	
    }