Snapchat OA

Problem1-word abbreviation

题意： 我们通常压缩的时候会把 interval 压缩成 i8l, 即首尾字母加这个word的长度。

1. 但是研究人员发现， internal 和 interval 如果按上面那种方法就会模糊不清，因为都会压缩成 i8l. 于是研究人员就想到一个办法，就是加长它们的prefix, 直到遇到它们第一个不同的字母， 比如：internal 和 interval 会压缩成： intern8l, interv8l. intension 和 intrusion 会变成： inte9n, intr9n
2. 当 压缩完后， 发现压缩后的长度 大于等于 原始长度时， 保留原始长度。比如 intern8l 长度也是 8， 那么就 保留原始： internal.

(例子我自己举的， 大概这意思)
input: 是一个 string like god internal me internet interval intension face intrusion
output: l2e god internal me i8t interval inte9n f2e intr9n (注意： 输出的时候要按照 输入string 的顺序， 顺序不能变)。

import java.util.*;

public class WordAbbr {
    public class TriNode {
        TriNode[] children;
        boolean isWord;
        int wordsCnt;
        public TriNode(){
            this.children = new TriNode[26];
            this.isWord = false;
            this.wordsCnt = 0;
        }
    }

    public String[] EncodeStr(String[] ipt){
        Map<String, TriNode> map = new HashMap<>();

        //build trie for input string
        for(String ea : ipt){
            int len = ea.length();
            String ptn = ""+ea.charAt(0)+len+ea.charAt(len-1);
            if(!map.containsKey(ptn)){
                TriNode crt = new TriNode();
                map.put(ptn,crt);
            }
            addToTrie(ea,map.get(ptn));
        }

        String[] rst = new String[ipt.length];
        //check for validation and start encoding
        for(int i=0;i<ipt.length;i++){
            int len = ipt[i].length();
            String ptn = ""+ipt[i].charAt(0)+len+ipt[i].charAt(len-1);
            TriNode root = map.get(ptn);
            String prefix = findPrefix(ipt[i],root);
            rst[i] = prefix.length()+2<len ? ""+prefix+len+ipt[i].charAt(len-1) : ipt[i];
        }
        return rst;
    }

    private void addToTrie(String s, TriNode root){
        TriNode idx = root;
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(idx.children[c-'a']==null)
                idx.children[c-'a'] = new TriNode();
            idx = idx.children[c-'a'];
            idx.wordsCnt++;
        }
        idx.isWord = true;
    }

    private String findPrefix(String s, TriNode root){
        StringBuilder prefix = new StringBuilder();
        TriNode idx = root;
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            idx = idx.children[c-'a'];
            prefix.append(c);
            if(idx.wordsCnt==1) return prefix.toString();
        }
        return prefix.toString();
    }
    public static void main(String[] args) {
        String[] ipt = {"like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"};
        WordAbbr test = new WordAbbr();
        String[] rst = test.EncodeStr(ipt);
        System.out.println(Arrays.toString(rst));
    }

}

Problem2-Valid Sudoku

LeetCode Link

import java.util.*;
public class ValidSudoku {

    public boolean isValidSudoku(char[][] board){
        for(int i=0;i<9;i++){
            HashSet<Character> row = new HashSet<>();
            HashSet<Character> col = new HashSet<>();
            HashSet<Character> cub = new HashSet<>();
            for(int j=0;j<9;j++){
                if(board[i][j]!='.' && !row.add(board[i][j])) return false;
                if(board[j][i]!='.' && !col.add(board[j][i])) return false;
                int rowcub = 3*(i/3);
                int colcub = 3*(i%3);
                if(board[rowcub+j/3][colcub+j%3]!='.' && !cub.add(board[rowcub+j/3][colcub+j%3])) return false;
            }
         }
         return true;
    }
    public static char[][] convert(String in) {
        char[][] result = new char[9][9];
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++) 
                result[i][j] = in.charAt(i * 9 + j);
        return result;
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        char[][] matrix = convert(sc.nextLine());
        ValidSudoku test = new ValidSudoku();
        if (test.isValidSudoku(matrix))
            System.out.println(1);
        else {
            System.out.println(0);
        }
    }

Problem3-Simple Word

import java.util.*;
public class SimpleWord {
    public boolean checkComp(String s, Set<String> wordDict) {
        if(s.length()==0) return false;
        boolean[] DP = new boolean[s.length()+1];
        DP[0]=true;
        for(int i=1;i<=s.length();i++){
            for(int j=0;j<i;j++){
                if(DP[j]&&wordDict.contains(s.substring(j,i))){
                    DP[i]=true; break;
                }
            }
        }
        return DP[s.length()];
    }
    public List<String> simpleWord(String[] ipt){
        List<String> rst = new ArrayList<>();
        HashSet<String> dict = new HashSet<>();
        for(String ea : ipt) dict.add(ea);
        for(String ea : ipt) {
            dict.remove(ea);
            if(!checkComp(ea,dict)){
                rst.add(ea);
            }
            dict.add(ea);
        }
        //or if output String[], output = rst.toArray(output);
        return rst;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cnt = sc.nextInt();
        String[] ipt = new String[cnt];
        for(int i=0;i<cnt;i++){
            ipt[i] = sc.next();
        }
        SimpleWord test = new SimpleWord();
        System.out.println(test.simpleWord(ipt));
    }
}