口试10大算法题汇总-字符串和数组2

面试10大算法题汇总-字符串和数组2

3.分词

给定一个字符串s和一个单词字典，确定s是否可被字典分解为多个单词

如：

给定s=”leetcode”

dict=[“leet”,”code”]

由于”leetcode”可被分割为”leet code”，返回True

最简单的一种方法是遍历dict中的单词，查看其是否在s的起始位置，若在则继续查看s剩下部分，否则返回false

import java.util.HashSet;
import java.util.Set;

public class test {
	public static boolean wordBreak(String s, Set<String> dict) {
		return wordBreakHelper(s, dict, 0);
	}

	public static boolean wordBreakHelper(String s, Set<String> dict, int start) {
		if(start == s.length())
			return true;
		for(String a:dict){
			int len = a.length();
			int end = len + start;
			//长度大于s，说明不可能是dict中的这个单词，遍历尝试dict中下一个单词
			if(end > s.length())
				continue;
			
			if(s.substring(start,end).equals(a))
				if(wordBreakHelper(s, dict, end))
					return true;
		}
		return false;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String s = "leetcode";
		Set<String> dict = new HashSet<String>();
		dict.add("leet");
		dict.add("code");
		
		System.out.println(wordBreak(s,dict));
	}
}

第二种方法为利用一个长度为s.length+1的bool型数组t，初始化时将t[0]设为true，其他设为false。

t[i] == true表示0~(i-1)可被分割，最后我们可以通过查看t[s.length()]的值判断s是否能被dict分割

import java.util.HashSet;
import java.util.Set;

public class test {
	public static boolean wordBreak(String s, Set<String> dict) {
        boolean[] t = new boolean[s.length()+1];
        t[0] = true; 
 
        for(int i=0; i<s.length(); i++){
            if(!t[i]) 
                continue;
 
            for(String a: dict){
                int len = a.length();
                int end = i + len;
                if(end > s.length())
                    continue;
 
                if(t[end]) continue;
 
                if(s.substring(i, end).equals(a)){
                    t[end] = true;
                }
            }
        }
 
        return t[s.length()];
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String s = "leetcode";
		Set<String> dict = new HashSet<String>();
		dict.add("leet");
		dict.add("code");
		
		System.out.println(wordBreak(s,dict));
	}
}

第三种方法为使用正则表达式

import java.util.HashSet;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class test {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		HashSet<String> dict = new HashSet<String>();
		dict.add("go");
		dict.add("goal");
		dict.add("goals");
		dict.add("special");
	 
		StringBuilder sb = new StringBuilder();
	 
		for(String s: dict){
			sb.append(s + "|");
		}
	 
		String pattern = sb.toString().substring(0, sb.length()-1);
		pattern = "("+pattern+")*";
		Pattern p = Pattern.compile(pattern);
		Matcher m = p.matcher("goalspecial");
	 
		if(m.matches()){
			System.out.println("match");
		}
	}
}

4.单词转化

给出两个单词start和end以及一个字典，求出从start转变到end的转变串的最小长度(每次只能改变单词中的一个字母，且改变后的单词必须是存在于dict中的)

如：

start = "hit"

end = "cog"

dict =["hot","dot","dog","lot","log"]

最短转变为"hit"-> "hot" -> "dot" -> "dog" -> "cog",转变串长度为5

注意：

无法转变时返回0、所有单词长度相同，且均为小写

本题可建立一个如下图所示的转化树：

然后求节点间距离即可。

解题思路：

申请两个List，一个用于存放单词节点(wordQueue)，一个用于存放步数distanceQueue。

第一步：将start加入wordQueue中，将1加入distanceQueue中，并将转化所需步数result初始化为Integer.MAX_VALUE。

之后开始核心步骤：

while(!wordQueue.isEmpty())

当wordQueue不为空时，逐个尝试队列中的单词(wordQueue.pop())，若弹出的单词为end，则说明转化成功，将此时所耗步骤与历史次数比较，取较小值。

观察其通过改变其中某个字母能否转变为dict中的其他单词。若能，则将转变后的单词存入wordQueue中，此时需注意，为防止陷入死循环(如hit->hot->hit->hot->...)，转变完成后需删除dict中的单词。

while执行完成后输出result

import java.util.HashSet;
import java.util.LinkedList;

public class test {
	public static int ladderLength(String start, String end,
			HashSet<String> dict) {
		if (dict.size() == 0)
			return 0;

		dict.add(end);

		LinkedList<String> wordQueue = new LinkedList<String>();
		LinkedList<Integer> distanceQueue = new LinkedList<Integer>();

		wordQueue.add(start);
		distanceQueue.add(1);

		// track the shortest path
		int result = Integer.MAX_VALUE;
		while (!wordQueue.isEmpty()) {
			String currWord = wordQueue.pop();
			Integer currDistance = distanceQueue.pop();

			if (currWord.equals(end)) {
				result = Math.min(result, currDistance);
			}

			for (int i = 0; i < currWord.length(); i++) {
				char[] currCharArr = currWord.toCharArray();
				for (char c = 'a'; c <= 'z'; c++) {
					currCharArr[i] = c;

					String newWord = new String(currCharArr);
					if (dict.contains(newWord)) {
						wordQueue.add(newWord);
						distanceQueue.add(currDistance + 1);
						dict.remove(newWord);
					}
				}
			}
		}

		if (result < Integer.MAX_VALUE)
			return result;
		else
			return 0;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		HashSet<String> dict = new HashSet<String>();
		dict.add("hot");
		dict.add("dot");
		dict.add("dog");
		dict.add("lot");
		dict.add("log");
		int i = ladderLength("hit", "cog", dict);
		System.out.println(i);
	}
}

口试10大算法题汇总-字符串和数组2

相关推荐