[LintCode] Twitch Words

zzbo 发布于2019-08-16 11:19 / 1338人阅读

Problem

Our normal words do not have more than two consecutive letters. If there are three or more consecutive letters, this is a tics. Now give a word, from left to right, to find out the starting point and ending point of all tics.

Example

Given str = "whaaaaatttsup", return [[2,6],[7,9]].

Explanation:
"aaaa" and "ttt" are twitching letters, and output their starting and ending points.
Given str = "whooooisssbesssst", return [[2,5],[7,9],[12,15]].

Explanation:
"ooo", "sss" and "ssss" are twitching letters, and output their starting and ending points.

Solution

public class Solution {
    /**
     * @param str: the origin string
     * @return: the start and end of every twitch words
     */
    public int[][] twitchWords(String str) {
        //set two boundaries, one pre value, only move the right boundary
        List> res = new ArrayList<>();
        int l = 0, r = 0;
        char[] strs = str.toCharArray();
        char pre = strs[0];
        for (int i = 0; i < strs.length; i++) {
            List cur = new ArrayList<>();
            if (i != 0 && strs[i] != pre) {
                if (r-l >= 2) {
                    cur.add(l);
                    cur.add(r);
                    res.add(cur);
                }
                l = i;
                r = i;
                pre = strs[i];
            } else if (strs[i] == pre) {
                r = i;
            }
        }
        //when the last three chars are twitch
        if (r-l >= 2) {
            List cur = new ArrayList<>();
            cur.add(l);
            cur.add(r);
            res.add(cur);
        }
        
        int[][] ans = new int[res.size()][2];
        for (int i = 0; i < res.size(); i++) {
            ans[i][0] = res.get(i).get(0);
            ans[i][1] = res.get(i).get(1);
        }
        return ans;
    }
}

混合云专线服务 Words LintCode Aspose.Words LintCode134_LRU

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71131.html

[LeetCode/LintCode] Top K Frequent Words

LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...

0x584a 2019-08-15 13:32 评论0 收藏0
[LeetCode/LintCode] Sentence Similarity

Problem Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar. For example, great acting skills a...

dreamtecher 2019-08-16 12:44 评论0 收藏0
[LintCode] Longest Words

Problem Given a dictionary, find all of the longest words in the dictionary. Example Given { dog, google, facebook, internationalization, blabla } the longest words are(is) [internationaliz...

roadtogeek 2019-08-14 15:15 评论0 收藏0
[LintCode] The Number In Words

Problem Given a non-negative integer n, print the number in words. Example Given n = 125 Return one hundred twenty five Solution class Solution { private String[] belowTen = new String[] {, One, T...

姘存按 2019-08-16 12:40 评论0 收藏0
[LeetCode/LintCode] Word Ladder

摘要：使用，利用其按层次操作的性质，可以得到最优解。这样可以保证这一层被完全遍历。每次循环取出的元素存为新的字符串。一旦找到和相同的字符串，就返回转换序列长度操作层数，即。 Problem Given two words (start and end), and a dictionary, find the length of shortest transformation sequence...

张金宝 2019-08-14 15:27 评论0 收藏0